目录
引入
1.中缀表达式的求值(两种方式)
方式一:使用两个栈直接求值
方式二:将其转换为后缀表达式求值
①转换:
②对后缀表达式求值:
2.后缀表达式的求值(1个栈,存放运算符)
3.前缀表达式的求值(1个栈用来存放数字,相对来讲没那么重要)
引入
1.中缀表达式的求值(两种方式)
方式一:使用两个栈直接求值
- 两个栈:运算对象(即运算数字)OPND和运算符OPTR
- 从左至右扫描表达式,直至表达式结束:
- 运算符与栈OPTR的栈顶元素比较优先级:
- 高:入栈OPTR
- 低或相等(不大于):运算对象OPND出栈顶两个元素,运算符OPTR出栈顶元素,进行运算(是次栈顶元素加减乘除栈顶元素!!!不要弄反了),运算结果入栈OPND(运算对象),直到当前运算符优先级高于栈顶元素。
- 运算对象:入栈OPND(运算对象)
- 运算符与栈OPTR的栈顶元素比较优先级:
- 当运算对象OPND只剩一个时,栈顶元素为运算结果
注意:左括号在栈外时认为其优先级最高;在栈内时认为其优先级最低。右括号在栈外认为其优先级最低。直到右括号与栈顶左括号优先级相等,左括号出栈。
过程演示:
①此时右括号准备入栈,但优先级最小,所以+号和4、2要出栈,进行运算。
4+2而不是2+4.