题解 | #四则运算#

背景知识

表达式的前、中、后缀表示方法的说明

what

所谓前中后即运算符位于操作数的前中后位置

why

中缀表达式适合人类理解，但不适合计算机去理解公式，因为中缀需要将整个表达式多次遍历完，确认运算符的优先级后才能作运算。但前后缀则不同，表达式输入完成后，计算机顺序读取即可，不用考虑优先级。

how

• 中缀转后缀

1. 初始化运算符栈S1和结果栈S2
2. 从左到右扫描中缀表达式
3. 遇到操作数时，压入S2
4. 遇到运算符时，与S1栈顶元素比较优先级，遵循 优先级高的在S1栈顶，优先级低或者相同的压入S2栈
   1. S1栈为空、入栈元素优先级高：直接入栈
   2. 入栈元素为(：直接入栈
   3. 入栈元素优先级低：S1栈顶压入S2，新的栈顶元素和入栈元素继续比较
   4. 入栈元素为)：S1栈顶到第一个(之间的元素依次弹出压入S2，完成后删除这一对括号
5. 遍历完成后，将S1依次弹出压入S2，此时S2出栈后逆序即为后缀表达式

中缀转前缀操作步骤和上述基一致，不同点在于

1. 由于前缀要求运算符在操作数前，所以应该从右往左进行扫描
2. 由于从右往左扫描，肯定是先遇到)再遇到(，故左右括号规则交替一下
3. 遇到相同优先级的，栈顶元素不出栈。这是从右往左扫描的缘故
4. S2出栈后无需逆序，即为前缀表达式

人工转换前中后缀表达式时，可以采用表达式的二叉树形式进行求解。例如，对于表达式a+b*c-(d+e)，其实画出二叉树之后，前缀和后缀表达式就是前序和后序遍历的结果

题解

说了这么多，这道题本质上是考中缀表达式的转换，但对于python来说，直接eval()就vans了...

import re

# exp = input()
exp = '3+2*{1+2*[-4/(8-6)+7]}'

# 替换为标准表达式
exp = re.sub(r'\{|\[', '(', exp)
exp = re.sub(r'\}|\]', ')', exp)

print(int(eval(exp)))        # 计算结果