Question

python实现中缀表达式转化为后缀表达式求值

Answer 1

首先维护两个空栈，（stack_exp）存放逆波兰表达式，(stack_ops)暂存操作符，运算结束后stack_ops必为空
循环遍历字符串(将表达式分为四种元素 1、数值; 2、操作符; 3、 左括号; 4、右括号)，具体情况如下
1、遇到数值， 将该值入栈stack_exp
2、遇到左括号， 将左括号入栈stack_ops
3、遇到右括号，将stack_ops中的操作符从栈顶依次出栈并入栈stack_exp， 直到第一次遇到左括号终止操作（注意： 该左括号出栈stack_ops但不入栈stack_exp）至此消除表达式中的一对括号
4、遇到四则运算操作符号（+ - * /）
4-1、 如果stack_ops为空， 操作符入栈stack_ops
4-2、 如果stack_ops不空，将stack_ops栈顶操作符与遍历到的操作符(op)比较：
4-2-1： 如果stack_ops栈顶操作符为左括或者op优先级高于栈顶操作符优先级， op入栈stack_ops，当前遍历结束
4-2-2： 如果op优先级小于或者等于stack_ops栈顶操作符， stack_ops栈顶操作符出栈并入栈stack_exp，重复4-1、 4-2直到op入栈stack_ops
5、字符串遍历结束后如果stack_ops栈不为空，则依次将操作符出栈并入栈stack_exp