中缀表达式转后缀表达式
时间: 2023-10-22 22:08:18 浏览: 30
中缀表达式是我们平时常用的表达式形式,例如 3 + 4 * 2 / ( 1 - 5 ) ^ 2 。而后缀表达式,也叫逆波兰表达式,是一种更加便于计算机处理的表达式形式。下面是中缀表达式转后缀表达式的算法步骤:
1. 创建一个空的栈和一个空的输出队列。
2. 从左到右扫描中缀表达式,如果遇到操作数,将其加入输出队列。
3. 如果遇到运算符,则进行如下处理:
a. 如果栈为空或栈顶元素为左括号,则将该运算符入栈。
b. 如果该运算符的优先级比栈顶运算符的优先级高,则将该运算符入栈。
c. 如果该运算符的优先级低于或等于栈顶运算符的优先级,则将栈顶运算符弹出并加入输出队列,然后回到步骤3继续比较。
4. 如果遇到左括号,则将其入栈。
5. 如果遇到右括号,则执行如下操作:
a. 不断弹出栈顶元素并加入输出队列,直到遇到左括号为止。
b. 将左括号弹出,但不加入输出队列。
6. 如果扫描到中缀表达式的末尾,则将栈中所有元素依次弹出并加入输出队列。
最终输出队列中的元素顺序即为转换后的后缀表达式。对于上面的中缀表达式,转换后的后缀表达式为 3 4 2 * 1 5 - 2 ^ / + 。