Golang栈结构和后缀表达式实现计算器示例

第Golang栈结构和后缀表达式实现计算器示例目录引言问题中缀、后缀表达式的计算人利用中缀表达式计算值计算机利用后缀表达式计算值计算后缀表达式的代码实现中缀表达式转后缀表达式转换过程转换的代码实现总结

引言

只进行基本的四则运算，利用栈结构和后缀表达式来计算数学表达式的值。

本文代码：GitHub

运行效果：

问题

如果只能进行两个值的加减乘除，如何编程计算一个数学表达式的值？

比如计算1+2*3+(4*5+6)*7，我们知道优先级顺序()大于*/大于+-，直接计算得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

}

现在只需知道如何将中缀转为后缀，再利用栈计算即可。

中缀表达式转后缀表达式

转换过程

从左到右逐个字符遍历中缀表达式，输出的字符序列即是后缀表达式：

遇到数字直接输出

遇到运算符则判断：

栈顶运算符优先级更低则入栈，更高或相等则直接输出栈为空、栈顶是(直接入栈运算符是)则将栈顶运算符全部弹出，直到遇见)中缀表达式遍历完毕，运算符栈不为空则全部弹出，依次追加到输出

转换的代码实现

//中缀表达式转后缀表达式

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向前跨越一个整数，由于执行了一步多余的j++，需要减1

default:

//操作符：遇到高优先级的运算符，不断弹出，直到遇见更低优先级运算符

for!stack.IsEmpty(){

top:=stack.Top()

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

break

postfix+=top

stack.Pop()

//低优先级的运算符入栈

stack.Push(char)

//栈不空则全部输出

for!stack.IsEmpty(){

postfix+=stack.Pop()

returnpostfix

//比较运算符栈栈顶top和新运算符newTop的优先级高低

funcisLower(topstring,newTopstring)bool{

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

switchtop{

case"+","-":

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

returntrue

case"(":

returntrue

returnfalse

}