只进行四则运算,利用栈结构和后缀表达式来计算数学表达式,支持使用 ()
改变运算符优先级。
本文代码:GitHub
运行效果:
问题
如果只能进行两个值的加减乘除,如何编程计算一个数学表达式的值?
比如计算 1+2*3+(4*5+6)*7
,我们知道优先级顺序 ()
大于* /
大于 + -
,直接计算得 1+6+26*7 = 189
中缀、后缀表达式的计算
人利用中缀表达式计算值
数学表达式的记法分为前缀、中缀和后缀记法,其中中缀就是上边的算术记法: 1+2*3+(4*5+6)*7
,人计算中缀表达式的值:把表达式分为三部分1
2+3
(4*5+6)*7
分别计算值,求和得 189。但这个理解过程在计算机上的实现就复杂了。
计算机利用后缀表达式计算值
中缀表达式 1+2*3+(4*5+6)*7
对应的后缀表达式: 123*+45*6+7*+
,计算机使用栈计算后缀表达式值:
计算后缀表达式的代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| func calculate(postfix string) int { stack := stack.ItemStack{} fixLen := len(postfix) for i := 0; i < fixLen; i++ { nextChar := string(postfix[i]) if unicode.IsDigit(rune(postfix[i])) { stack.Push(nextChar) } else { num1, _ := strconv.Atoi(stack.Pop()) num2, _ := strconv.Atoi(stack.Pop()) switch nextChar { 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()) return result }
|
现在只需知道如何将中缀转为后缀,再利用栈计算即可。
中缀表达式转后缀表达式
转换过程
从左到右逐个字符遍历中缀表达式,输出的字符序列即是后缀表达式:
遇到数字直接输出
遇到运算符则判断:
- 栈为空、栈顶是
(
直接入栈
- 运算符是
)
则将栈顶运算符全部弹出,直到遇见 )
中缀表达式遍历完毕,运算符栈不为空则全部弹出,依次追加到输出
转换的代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
| func infix2ToPostfix(exp string) string { stack := stack.ItemStack{} postfix := "" expLen := len(exp)
for i := 0; i < expLen; i++ {
char := string(exp[i])
switch char { case " ": continue case "(": stack.Push("(") case ")": for !stack.IsEmpty() { preChar := stack.Top() if preChar == "(" { stack.Pop() break } postfix += preChar stack.Pop() }
case "0", "1", "2", "3", "4", "5", "6", "7", "8", "9": j := i digit := "" for ; j < expLen && unicode.IsDigit(rune(exp[j])); j++ { digit += string(exp[j]) } postfix += digit i = j - 1
default: for !stack.IsEmpty() { top := stack.Top() if top == "(" || isLower(top, char) { break } postfix += top stack.Pop() } stack.Push(char) } }
for !stack.IsEmpty() { postfix += stack.Pop() }
return postfix }
func isLower(top string, newTop string) bool { switch top { case "+", "-": if newTop == "*" || newTop == "/" { return true } case "(": return true } return false }
|
总结
计算机计算数学表达式的值分成了 2 步,利用 stack 将人理解的中缀表达式转为计算机理解的后缀表达式,再次利用 stack 计算后缀表达式的值。