计算中缀表达式
1概念
什么是中缀表达式,什么是后缀表达式?
从小学开始学习的四则运算,例如:3+(5(2+3)+7) 类似这种表达式就是中缀表达式。中缀表达式人脑很容易理解,各个算符的优先级,人脑也很容易判断,先算括弧里的,再算,再算+,-
但是这种表达式很不利于计算机计算,通过某种方式把前缀表达式转换为后缀表达式方便计算机进行计算,如3+(5(2+3)+7)的后缀表达式就是3,5,2,3,+,,7,+, +。这个表达式计算机很容易计算,为什么容易计算,通过算法流程2,就会一个深入的理解。
2算法流程
如何把中缀表达式转换成后缀表达式?比如说3+(5*(2+3)+7)的转成后缀表达式的流程如何?
操作符优先级:
+,- 小于*,/
+ 等于 -
* 等于 /
左括号和右括号作为特殊操作符特殊处理。(碰到’(’不用判断优先级直接入操作符栈,碰到’)’,也不用判断优先级,直接出操作符栈)
大致算法掌握以下几个流程:
准备两个栈,一个是数字栈A,一个是操作符栈(+,-,*,/(,))B等
1.0 对于数字栈A,遇到数字直接入栈A。
2.0 对于操作符栈B,分几种情况
2.1 碰到 ‘(‘操作符直接入栈
2.2 碰到 ‘)’操作符,不停的把操作符栈B出栈,直到遇到’)’。(把’(’到’)’之间的弹出的操作符依次入栈A)
2.3 碰到’+,-,* /’比较当前元素(假设当前元素current)和B栈栈顶的操作符(假设栈顶元素是top)的优先级.
2.3.1 如果top >= current, B栈出栈且循环比较,直到top < current退出循环,且把 current入栈
2.3.2 如果top < current, 直接把current入B栈
3.0 扫描完整个字符串,如果B栈中还有操作符,依次出栈入A
按照上面算法演示3+(5*(2+3)+7)的流程:
1,碰到3,3入A栈 [3,]
2,碰到+,入B栈 [+,]
3,碰到(,入B栈 [+,(]
4,碰到5,入A栈 [3,5]
5,碰到,的优先级大于 (,入B栈[ +,(,]
6,碰到(,入B栈[ +,(,,(]
7,碰到2,入A栈 [3,5,2]
8,碰到+,入B栈[ +,(,,(,+]
9,碰到3,入A栈 [3,5,2,3]
10,碰到),弹出B栈,直接到 ‘(‘,把弹出的操作符入A栈。B:[ +,(,] A:[3,5,2,3,+]
11,碰到+, +的优先级小于B的栈顶元素 ,所以从B出栈,入A,并把+入B。B:[ +,(,+] A:[3,5,2,3,+,]
12,碰到7,入A栈 [3,5,2,3,+,,7]
13,碰到),弹出B栈,直接到 ‘(‘,把弹出的操作符入A栈。B:[ +] A:[3,5,2,3,+,,7,+]
14, 扫描完整个字符串,判断B是否为空,不为空把B栈的元素弹出,入A。当前不为空,所以最终A栈的元素为 A:[3,5,2,3,+,,7,+, +]
所以最终A的后缀表达式是3,5,2,3,+,*,7,+, +
计算机拿到这个会怎么计算呢?流程如下:
碰到数字直接入栈碰到操作符,直接弹出两个栈顶元素,通过操作符计算,把结果压入栈
通过步骤1,2循环计算,最终栈里只会有一个元素,这个就是表达式的结果。
我们来演练一下:
1,碰到数字3,5,2,3直接入栈A[3,5,2,3]
2,碰到+,弹出栈顶2,3,相加得5 入栈A[3,5,5]
3,碰到*,弹出栈顶5,5,相乘得25 入栈A[3,25]
4,碰到7,直接入栈A[3,25,7]
5,碰到+,弹出栈顶25,7,相加得32 入栈A[3,32]
6,碰到+,弹出栈顶3,32,相加得35 入栈A[35]
通过上面可以得知,计算机很容易计算,从左扫描到右就能把结果得出。