中缀表达式
9 + (3 - 1)*3 + 8 / 2
后缀表达式
9 3 1 - 3 * + 8 2 / +
简易计算器，可以通过栈来实现。然而如果直接使用中缀表达式，需要处理括号，而使用后缀表达式则可以规避这种麻烦。后缀表达式计算起来更加方便，步骤如下：
1.将后缀表达式入栈，数字直接入栈
2.遇到操作符，将栈顶的两个元素出栈，
第一个出栈的是操作数，第二个出栈的是被操作数，
根据操作符计算两个数的结果，然后将结果再次入栈
3.重复上面的步骤，直到后缀表达式遍历结束，最后在栈中的元素便是计算结果
例：9 3 1 - 3 * + 8 2 / +
第一步：
后缀表达式的第一个元素是9，数字直接入栈。
第二步：
后缀表达式的第二个元素3，数字直接入栈。
第三步：
后缀表达式的第三个元素1，数字直接入栈。
第四步：
后缀表达式的第四个元素‘-’，将栈顶的两个元素出栈，
第一个出栈的1作为操作数，第二个出栈的3作为被操作数，
而操作符是‘-’，计算结果为：3 - 1 = 2，然后将2入栈。
第五步：
后缀表达式的第五个元素3，数字直接入栈。
第六步：
后缀表达式的第六个元素‘*’，将栈顶的两个元素出栈，
第一个出栈的3作为操作数，第二个出栈的2作为被操作数，
而操作符是‘-’，计算结果为：2 * 3 = 6，然后将6入栈。
第七步：
后缀表达式的第七个元素‘+’，将栈顶的两个元素出栈，
第一个出栈的6作为操作数，第二个出栈的9作为被操作数，
而操作符是‘-’，计算结果为：9 + 6 = 15，然后将15入栈。
第八步：
后缀表达式的第八个元素8，数字直接入栈。
第九步：
后缀表达式的第九个元素2，数字直接入栈。
第十步：
后缀表达式的第十个元素‘/’，将栈顶的两个元素出栈，
第一个出栈的2作为操作数，第二个出栈的8作为被操作数，
而操作符是‘-’，计算结果为：8 / 2 = 4，然后将4入栈。
第十一步：
后缀表达式的第十一个元素‘/’，将栈顶的两个元素出栈，
第一个出栈的4作为操作数，第二个出栈的15作为被操作数，
而操作符是‘-’，计算结果为：15 + 4 = 19，然后将19入栈。
第十二步：
后缀表达式遍历结束，栈中的元素就是最后的计算结果。
在了解了后缀表达式的计算过程，我们可以通过栈轻松实现该计算过程，那如何将中缀表达式转化成后缀表达式？
中缀表达式转化为后缀表达式
规则：从左到右遍历中缀表达式的数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级。是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
具体实现步骤：中缀表达式转化为后缀表达式可以通过栈和队列来实现，
需要一个栈，用来存操作符，需要一个队列，用来存后缀表达式的结果。
1.遍历中缀表达式，如果是数字则直接入后缀表达式队列
2.如果操作符栈为空，操作符直接入操作符栈
3.如果操作符的优先级大于操作符栈顶元素的优先级，则直接入栈，
否则栈顶元素出栈，并添加到后缀表达式队列中，直到栈顶元素小于操作符的优先级，然后将该操作符入栈到操作符栈
4.如果操作符是右括号，操作符做出栈操作，且添加到后缀表达式队列中，
直到左括号出栈，左括号不需添加到后缀表达式队列中
5.中缀表达式遍历结束，需将操作符栈的元素依次出栈，并添加到后缀表达式队列中
例：9 + (3 - 1)*3 + 8 / 2
第一步：
中缀表达式的第一个元素是9，数字直接入后缀表达式队列
结果：
中缀表达式队列：9
操作符栈：null
第二步：
中缀表达式的第二个元素是‘+’，操作符栈为空，符号‘+’直接入栈
结果：
中缀表达式队列：9
操作符栈：+
第三步：
中缀表达式的第三个元素是‘（’，括号的优先级大于操作符栈顶元素，‘（’直接入栈
结果：
中缀表达式队列：9
操作符栈：+ （
第四步：
中缀表达式的第四个元素是3，数字直接入后缀表达式队列
结果：
中缀表达式队列：9 3
操作符栈：+ （
第五步：
中缀表达式的第五个元素是‘-’，
由于栈顶元素是‘（’操作符，‘（’操作符只有遇到‘）’操作符才会出栈，
故‘-’直接入栈
结果：
中缀表达式队列：9 3
操作符栈：+ （ -
第六步：
中缀表达式的第六个元素是1，数字直接入后缀表达式队列
结果：
中缀表达式队列：9 3 1
操作符栈：+ （ -
第七步：
中缀表达式的第七个元素是‘）’，遇到右括号，栈顶元素依次出栈，
并入到后缀表达式队列中，直到‘（’出栈，‘（’出栈后不做处理
结果：
中缀表达式队列：9 3 1 -
操作符栈：+
第八步：
中缀表达式的第八个元素是‘*’，优先级高于操作符栈栈顶元素‘+’的优先级，故直接入栈
结果：
中缀表达式队列：9 3 1 -
操作符栈：+ *
第九步：
中缀表达式的第九个元素是3，数字直接入后缀表达式队列
结果：
中缀表达式队列：9 3 1 - 3
操作符栈：+ *
第十步：
中缀表达式的第十个元素是‘+’，优先级不大于操作符栈栈顶元素，
栈顶元素出栈，并入到后缀表达式队列中，
直到栈顶元素的优先级小于该元素的优先级，最后该元素入栈到操作符栈
结果：
中缀表达式队列：9 3 1 - 3 * +
操作符栈：+
第十一步：
中缀表达式的第十一个元素是8，数字直接入后缀表达式队列
结果：
中缀表达式队列：9 3 1 - 3 * + 8
操作符栈：+
第十二步：
中缀表达式的第十二个元素是‘/’，优先级高于操作符栈栈顶元素的优先级，故直接入栈
结果：
中缀表达式队列：9 3 1 - 3 * + 8
操作符栈：+ /
第十三步：
中缀表达式的第十三个元素是2，数字直接入后缀表达式队列
结果：
中缀表达式队列：9 3 1 - 3 * + 8 2
操作符栈：+ /
第十四步：
中缀表达式遍历结束，将操作符栈栈顶元素依次出栈，并入到后缀表达式的队列中
结果：
中缀表达式队列：9 3 1 - 3 * + 8 2 / +
操作符栈：null
代码
class Calculator(object):
def __init__(self):
# 操作符集合
self.operators = ['+', '-', '*', '/', '(', ')']
# 操作符优先级
self.priority = {
'+': 1,
'-': 1,
'*': 2,
'/': 2,
'(': 3,
')': 3
}
def generate_postfix_expression(self, expression):
"""
生成后缀表达式
:param expression:
:return:
"""
# 去除表达式中所有空格
expression = expression.replace(' ', '')
# 创建list作为栈，list的append和pop方法刚好和栈的入栈和出栈方法相同
# 操作符栈
operator_stack = list()
# 后缀表达式是从尾部插入数据，使用后缀表达式计算结果是从头开始遍历，可以理解为先进先出，可以使用队列实现，
# 这里为了简便用list代替，不做内存释放处理
expression_stack = list()
for element in expression:
# 如果是数字则直接入表达式栈
if element in self.operators:
# 如果栈为空，操作符直接入操作符栈，或者为左括号，也直接入操作符栈
if not operator_stack:
operator_stack.append(element)
else:
# 如果目标元素是右括号，操作符栈顶出栈直接遇到左括号，且出栈的操作符除了括号入到表达式队列中
if element == ')':
for top in operator_stack[::-1]:
if top != '(':
expression_stack.append(top)
operator_stack.pop()
else:
operator_stack.pop()
break
else:
for top in operator_stack[::-1]:
# 如果目标元素大于栈顶元素，则直接入栈，否则栈顶元素出栈，入到表达式队列中
# 左括号只有遇到右括号才出栈
if self.priority[top] >= self.priority[element] and top != '(':
expression_stack.append(top)
operator_stack.pop()
else:
operator_stack.append(element)
break
# 可能操作符栈所有的元素优先级都大于等于目标操作符的优先级，这样的话操作符全部出栈了，
# 而目标操作符需要入栈操作
if not operator_stack:
operator_stack.append(element)
else:
expression_stack.append(element)
# 中缀表达式遍历结束，操作符栈仍有操作符，将操作符栈中的操作符入到表达式栈中
for i in range(len(operator_stack)):
expression_stack.append(operator_stack.pop())
return expression_stack
def calcaulate(self, expression):
# 生成后缀表达式
expression_result = self.generate_postfix_expression(expression)
# 使用list作为栈来计算
calcalate_stack = list()
# 遍历后缀表达式
for element in expression_result:
# 如果为数字直接入栈
# 遇到操作符，将栈顶的两个元素出栈
if element not in self.operators:
calcalate_stack.append(element)
else:
# 操作数
number1 = calcalate_stack.pop()
# 被操作数
number2 = calcalate_stack.pop()
# 结果 = 被操作数 操作符 操作数 （例：2 - 1）
result = self.operate(number1, number2, element)
# 计算结果入栈
calcalate_stack.append(result)
return calcalate_stack[0]
def operate(self, number1, number2, operator):
"""
计算结果
:param number1: 操作数
:param number2: 被操作数
:param operator: 操作符
:return:
"""
number1 = int(number1)
number2 = int(number2)
if operator == '+':
return number2 + number1
if operator == '-':
return number2 - number1
if operator == '*':
return number2 * number1
if operator == '/':
return number2 / number1
if __name__ == '__main__':
c = Calculator()
expression = '9 + (3 - 1)*3 + 8 / 2'
expression_result = c.calcaulate(expression)
print(expression_result)
代码还有许多小问题，还需要优化，比如时间复杂度还要降低，中缀表达式没法正确拆分，数字是十位以上的就会出错了，十位个位等会被拆成单个字符。
网友评论