Golang棧結(jié)構(gòu)和后綴表達(dá)式實(shí)現(xiàn)計(jì)算器示例

第Golang棧結(jié)構(gòu)和后綴表達(dá)式實(shí)現(xiàn)計(jì)算器示例目錄引言問題中綴、后綴表達(dá)式的計(jì)算人利用中綴表達(dá)式計(jì)算值計(jì)算機(jī)利用后綴表達(dá)式計(jì)算值計(jì)算后綴表達(dá)式的代碼實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式轉(zhuǎn)換過程轉(zhuǎn)換的代碼實(shí)現(xiàn)總結(jié)

引言

只進(jìn)行基本的四則運(yùn)算，利用棧結(jié)構(gòu)和后綴表達(dá)式來計(jì)算數(shù)學(xué)表達(dá)式的值。

本文代碼：GitHub

運(yùn)行效果：

問題

如果只能進(jìn)行兩個(gè)值的加減乘除，如何編程計(jì)算一個(gè)數(shù)學(xué)表達(dá)式的值？

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

中綴、后綴表達(dá)式的計(jì)算

人利用中綴表達(dá)式計(jì)算值

數(shù)學(xué)表達(dá)式的記法分為前綴、中綴和后綴記法，其中中綴就是上邊的算術(shù)記法：1+2*3+(4*5+6)*7，人計(jì)算中綴表達(dá)式的值：把表達(dá)式分為三部分12+3(4*5+6)*7分別計(jì)算值，求和得189。但這個(gè)理解過程在計(jì)算機(jī)上的實(shí)現(xiàn)就復(fù)雜了。

計(jì)算機(jī)利用后綴表達(dá)式計(jì)算值

中綴表達(dá)式1+2*3+(4*5+6)*7對(duì)應(yīng)的后綴表達(dá)式：123*+45*6+7*+，計(jì)算機(jī)使用棧計(jì)算后綴表達(dá)式值：

計(jì)算后綴表達(dá)式的代碼實(shí)現(xiàn)

funccalculate(postfixstring)int{

stack:=stack.ItemStack{}

fixLen:=len(postfix)

fori:=0;ifixLen;i++{

nextChar:=string(postfix[i])

//數(shù)字：直接壓棧

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

stack.Push(nextChar)

}else{

//操作符：取出兩個(gè)數(shù)字計(jì)算值，再將結(jié)果壓棧

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

}

現(xiàn)在只需知道如何將中綴轉(zhuǎn)為后綴，再利用棧計(jì)算即可。

中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

轉(zhuǎn)換過程

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

遇到數(shù)字直接輸出

遇到運(yùn)算符則判斷：

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

轉(zhuǎn)換的代碼實(shí)現(xiàn)

//中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

funcinfix2ToPostfix(expstring)string{

stack:=stack.ItemStack{}

postfix:=""

expLen:=len(exp)

//遍歷整個(gè)表達(dá)式

fori:=0;iexpLen;i++{

char:=string(exp[i])

switchchar{

case"":

continue

case"(":

//左括號(hào)直接入棧

stack.Push("(")

case")":

//右括號(hào)則彈出元素直到遇到左括號(hào)

for!stack.IsEmpty(){

preChar:=stack.Top()

ifpreChar=="("{

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

break

postfix+=preChar

stack.Pop()

//數(shù)字則直接輸出

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向前跨越一個(gè)整數(shù)，由于執(zhí)行了一步多余的j++，需要減1

default:

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

for!stack.IsEmpty(){

top:=stack.Top()

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

break

postfix+=top

stack.Pop()

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

stack.Push(char)

//棧不空則全部輸出

for!stack.IsEmpty(){

postfix+=stack.Pop()

returnpostfix

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

funcisLower(topstring,newTopstring)bool{

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

switchtop{

case"+","-":

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

returntrue

case"(":

returntrue

returnfalse

}