Skip to content

Latest commit

 

History

History
38 lines (27 loc) · 1.98 KB

Lesson-35.md

File metadata and controls

38 lines (27 loc) · 1.98 KB

Lesson 35 - 表达式求值问题

课程任务

学习逆波兰表达式的概念,使用栈这种数据结构作为操作数缓存区,计算后缀表达式的值。

例如 12+34+ 和 123+4- ,结果分别为 13 和 3。

后缀表达式计算规则如下:

1. 如果是操作数,则放入栈中;
2. 如果是操作符,则取出栈中两个操作数,进行运算后,将结果放入栈中;
3. 直到最后栈中只有一个元素,此元素就是计算结果;
  • 提示:只需要考虑实现加减乘除四则运算,所有数字都是1个字符的情况。

提高要求

使用2个栈--操作数栈和操作符栈,实现将中缀表达式转换为后缀形式,并实现求值。

例如 5 + ((1 + 2) * 4) - 3 => 5 1 2 + 4 * + 3 - => 14

中缀表达式转换成后缀表达式,此方法需要遵循规则如下:

1. 如果读入操作数,则直接放入输出字符串;
2. 如果读入一般运算符如+-*/,则放入堆栈,但是放入堆栈之前必须要检查栈顶,并确定栈顶运算符的优先级比放入的运算符的优先级低;
   如果放入的优先级较低,则需要将栈顶的运算符放入输出字符串;
3. 如果读入(,因为左括号优先级最高,因此放入栈中,但是注意,当左括号放入栈中后,则优先级最低;
4. 如果读入),则将栈中运算符取出放入输出字符串,直到取出(为止,注意:()不输出到输出字符串;
5. 顺序读完表达式,如果栈中还有操作符,则弹出,并放入输出字符串;

重要知识点

  • 逆波兰表达式
  • 后缀表示法

参考资料