栈应用之四则运算

四则运算

四则运算表达式是我们小学就接触的内容,它遵循“先乘除,后加减,从左到右,括号内先算”的法则,例如“7 + (5 - 3) * 4 + 6 / 3”,这个表达式先算5 - 32,再算2 * 46 / 3,最后计算7 + 8 +2,这个过程很简单,口算就能完成,但是如果让我们在程序里实现这个功能,该如何实现呢?我们遇到的困难在于乘除优在加减的后面,却要先运算,另外还要考虑括号,问题就复杂了。

后缀表达式

波兰有位科学家也想到了这个问题,他想出了一种新的不需要括号的表达式:“后缀表达式”,它更有利于计算机计算。让我们看看它的样子:对于“7 + (5 - 3) * 4 + 6 / 3”,后缀表达式为“7 5 3 - 4 * + 6 3 / +”,叫后缀的原因在于运算符在操作数之后。我们人类喜欢看到的表达式叫“中缀表达式”(因为运算符在操作数中间),但是计算机不喜欢它。

后缀表达式的方法

为了看到后缀表达式的好处,我们先看看,计算机如何利用后缀表达式计算出最终结果。 * 后缀表达式:7 5 3 - 4 * + 6 3 / + * 规则:从左到右遍历字符串,遇到数字则进栈,遇到符号则将栈顶的两个数字出栈,进行计算,运算结果进栈,一直到最终获得结果。

  1. 初始化一个空栈,此栈用来对要运算的数字进出使用。
  2. 字符串中前三个都是数字,所以7,5,3进栈。
过程
  1. 接下来是“-”,所以5和3出栈,5作为被减数,3作为减数,5减3得到2,并将2入栈。
  2. 接着是4入栈。
过程
  1. 接下来是”*“,所以4和2出栈,4乘以2得8,8入栈。
  2. 下面是“+”,7和8出栈,7加8得15,15入栈。
过程
  1. 接下来6和3数字入栈。
  2. 遇到符号“/”,所以6和3出栈,6作为被除数,3作为除数,6除3得2,2入栈。
过程
  1. 最后遇到符号“+”,15和2出栈,15加2得17,17入栈,遍历结束,将最后结果出栈,得到17。
过程

中缀表达式转后缀表达式

可以看到利用就很容易计算后缀表达式的值,那么现在我们的问题就是中缀转后缀。

  • 中缀表达式:“8 + (7 - 2 * 3 + 2) * 3 + 10 / 2”
  • 规则:遍历字符串,遇到数字则输出,即成为后缀表达式一部分;若是操作符,则判断与栈顶符号的优先级(乘除优先级比加减优先级高,乘除优先级一样,加和减也一样),如果高于栈顶符号,则压栈,否则从栈顶开始弹出元素直到遇到遇到优先级更低的符号(或者遇到“(”,“(”只有遇到“)”才会弹出),弹出完这些符号后,把当前符号压栈。
  1. 初始化一空栈,用来对符号进出栈使用。
  2. 第一个字符是数字8,输出8,后面符号是“+”,进栈。
过程
  1. 第三个字符是“(”,因为是左括号,所以压栈,第四个字符是7,输出,总表达式为8 7。
  2. 接着是“-”,因为栈顶是“(”,所以压栈。后面字符是2,输出,总表达式为8 7 2。
过程
  1. 之后符号是“*”,它的优先级比栈顶“-”高,所以压栈,再之后是数字3,输出,总表达式为8 7 2 3。
  2. 接着是符号“+”,它比“*”的优先级低,所以“*”弹出栈输出,而“-”优先级和“+”一样,也要弹出栈输出,接下来碰到符号“(”,就要把“+”压栈。接着是数字2,输出,总表达式为8 7 2 3 * - 2。
过程
  1. 接着是符号“)”,这时需要从栈顶开始依次弹出符号输出,直到遇到“(”(“(”也要弹出,只是不输出),“(”之后只剩一个“+”,所以弹出“+”输出,接下来是符号“*”,优先级比“+”高,所以压栈,总表达式为8 7 2 3 * - 2 +。
  2. 接下来是数字3,输出,紧接着是符号“+”,它比栈顶“*”优先级低,所以弹出“*”输出,而之后比较的“+”优先级一样,也弹出栈输出,最后“+”压栈,总表达式为8 7 2 3 * - 2 + 3 * +。
过程
  1. 接着是数字10,输出,接下来是符号“/”,比符号“+”优先级高,所以压栈,总表达式为8 7 2 3 * - 2 + 3 * + 10。
  2. 接着是数字2,输出。遍历结束,依次弹出栈中元素,最后总表达式为8 7 2 3 * - 2 + 3 * + 10 2 / +。
过程

代码示例

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
76
77
78
79
80
81
82
83
// 预先生成运算符的tokens
prepareTokens() {
this.tokens = [
new Token('#', TOKEN_TYPE.ENDEXPR),
new Token('(', TOKEN_TYPE.LEFTPAREN),
new Token(')', TOKEN_TYPE.RIGHTPAREN),
new Token('~', TOKEN_TYPE.UNARYOP, 6), // 负号
new Token('abs', TOKEN_TYPE.UNARYOP, 6), // 求绝对值
new Token('sqrt', TOKEN_TYPE.UNARYOP, 6), // 开平方根
new Token('exp', TOKEN_TYPE.UNARYOP, 6), // e的x次
new Token('ln', TOKEN_TYPE.UNARYOP, 6), // e为底数的对数
new Token('log10', TOKEN_TYPE.UNARYOP, 6), // 10为底数的对数
new Token('sin', TOKEN_TYPE.UNARYOP, 6), // 求sin x
new Token('cos', TOKEN_TYPE.UNARYOP, 6), // 求cos x
new Token('tan', TOKEN_TYPE.UNARYOP, 6), // 求tan x
new Token('+', TOKEN_TYPE.BINARYOP, 4), // 二元+
new Token('-', TOKEN_TYPE.BINARYOP, 4), // 二元-
new Token('*', TOKEN_TYPE.BINARYOP, 5), // 乘法
new Token('/', TOKEN_TYPE.BINARYOP, 5), // 除法
new Token('%', TOKEN_TYPE.BINARYOP, 5), // 除模取余
new Token('^', TOKEN_TYPE.BINARYOP, 6), // 指数运算
]
}

/**
* 中缀表达式转化为后缀表达式
* @return {Array}
*/
transform() {
const postExp = []
const opStack = []
for (let i = 0; i < this.infixExp.length; i++) {
const pos = this.infixExp[i]
const token = this.tokens[pos]
switch (token.type) {
case TOKEN_TYPE.OPRAND:
postExp.push(pos)
break;
case TOKEN_TYPE.LEFTPAREN: // “(”直接入栈
opStack.push(pos)
break;
case TOKEN_TYPE.RIGHTPAREN: // 为“)”,出栈直到遇到运算符“(”
let prePos = opStack.pop()
while (prePos in this.tokens && opStack.length >= 0 &&
this.tokens[prePos].type !== TOKEN_TYPE.LEFTPAREN) {
postExp.push(prePos)
prePos = opStack.pop()
}
break;
case TOKEN_TYPE.UNARYOP:
case TOKEN_TYPE.BINARYOP:
let endright = 0
while (endright === 0) {
if (opStack.length <= 0)
endright = 1
else if (this.tokens[opStack[opStack.length - 1]].type === TOKEN_TYPE.LEFTPAREN) {
endright = 1
} else if (this.tokens[opStack[opStack.length - 1]].priority < token.priority) {
endright = 1
} else if (this.tokens[opStack[opStack.length - 1]].priority === token.priority &&
token.priority === MAX_PRIORITY) {
endright = 1
} else {
postExp.push(opStack.pop())
endright = 0
}
}
opStack.push(pos)
break
case TOKEN_TYPE.ENDEXPR:
while (opStack.length >= 1) {
postExp.push(opStack.pop())
}
break
default:
break
}
}

postExp.push(0) // 添加终止符
return postExp
}

中缀表达式infixExp中存的是this.tokens中的索引,完整代码Github