Golang棧結構和后綴表達式實現計算器示例

第Golang棧結構和后綴表達式實現計算器示例目錄引言問題中綴、后綴表達式的計算人利用中綴表達式計算值計算機利用后綴表達式計算值計算后綴表達式的代碼實現中綴表達式轉后綴表達式轉換過程轉換的代碼實現總結

引言

只進行基本的四則運算，利用棧結構和后綴表達式來計算數學表達式的值。

本文代碼：GitHub

運行效果：

問題

如果只能進行兩個值的加減乘除，如何編程計算一個數學表達式的值？

比如計算1+2*3+(4*5+6)*7，我們知道優(yōu)先級順序()大于*/大于+-，直接計算得1+6+26*7=189

中綴、后綴表達式的計算

人利用中綴表達式計算值

數學表達式的記法分為前綴、中綴和后綴記法，其中中綴就是上邊的算術記法：1+2*3+(4*5+6)*7，人計算中綴表達式的值：把表達式分為三部分12+3(4*5+6)*7分別計算值，求和得189。但這個理解過程在計算機上的實現就復雜了。

計算機利用后綴表達式計算值

中綴表達式1+2*3+(4*5+6)*7對應的后綴表達式：123*+45*6+7*+，計算機使用棧計算后綴表達式值：

計算后綴表達式的代碼實現

funccalculate(postfixstring)int{

stack:=stack.ItemStack{}

fixLen:=len(postfix)

fori:=0;ifixLen;i++{

nextChar:=string(postfix[i])

//數字：直接壓棧

ifunicode.IsDigit(rune(postfix[i])){

stack.Push(nextChar)

}else{

//操作符：取出兩個數字計算值，再將結果壓棧

num1,_:=strconv.Atoi(stack.Pop())

num2,_:=strconv.Atoi(stack.Pop())

switchnextChar{

case"+":

stack.Push(strconv.Itoa(num1+num2))

case"-":

stack.Push(strconv.Itoa(num1-num2))

case"*":

stack.Push(strconv.Itoa(num1*num2))

case"/":

stack.Push(strconv.Itoa(num1/num2))

result,_:=strconv.Atoi(stack.Top())

returnresult

}

現在只需知道如何將中綴轉為后綴，再利用棧計算即可。

中綴表達式轉后綴表達式

轉換過程

從左到右逐個字符遍歷中綴表達式，輸出的字符序列即是后綴表達式：

遇到數字直接輸出

遇到運算符則判斷：

棧頂運算符優(yōu)先級更低則入棧，更高或相等則直接輸出棧為空、棧頂是(直接入棧運算符是)則將棧頂運算符全部彈出，直到遇見)中綴表達式遍歷完畢，運算符棧不為空則全部彈出，依次追加到輸出

轉換的代碼實現

//中綴表達式轉后綴表達式

funcinfix2ToPostfix(expstring)string{

stack:=stack.ItemStack{}

postfix:=""

expLen:=len(exp)

//遍歷整個表達式

fori:=0;iexpLen;i++{

char:=string(exp[i])

switchchar{

case"":

continue

case"(":

//左括號直接入棧

stack.Push("(")

case")":

//右括號則彈出元素直到遇到左括號

for!stack.IsEmpty(){

preChar:=stack.Top()

ifpreChar=="("{

stack.Pop()//彈出"("

break

postfix+=preChar

stack.Pop()

//數字則直接輸出

case"0","1","2","3","4","5","6","7","8","9":

j:=i

digit:=""

for;jexpLenamp;amp;unicode.IsDigit(rune(exp[j]));j++{

digit+=string(exp[j])

postfix+=digit

i=j-1//i向前跨越一個整數，由于執(zhí)行了一步多余的j++，需要減1

default:

//操作符：遇到高優(yōu)先級的運算符，不斷彈出，直到遇見更低優(yōu)先級運算符

for!stack.IsEmpty(){

top:=stack.Top()

iftop=="("||isLower(top,char){

break

postfix+=top

stack.Pop()

//低優(yōu)先級的運算符入棧

stack.Push(char)

//棧不空則全部輸出

for!stack.IsEmpty(){

postfix+=stack.Pop()

returnpostfix

//比較運算符棧棧頂top和新運算符newTop的優(yōu)先級高低

funcisLower(topstring,newTopstring)bool{

//注意a+b+c的后綴表達式是ab+c+，不是abc++

switchtop{

case"+","-":

ifnewTop=="*"||newTop=="/"{

returntrue

case"(":

returntrue

returnfalse

}