栈的应用（表达式求值）

文章目录三种表达式的形式中缀表达式 转 后缀表达式手算方法机算中缀表达式 转 前缀表达式手算方法机算总结算数表达式由三部分组成操作数、运算符、界限符界限符是必不可少的反映了计算的先后顺序三种表达式的形式首先要分清三种表达式的写法这是所有计算的基础注意数字出现的左右先后顺序不能改变。表达式类型定义示例12 )和 (34)*5特点中缀表达式Infix运算符在两个操作数中间1 2(3 4) * 5人类习惯但计算机难处理需处理括号和优先级。后缀表达式逆波兰RPN运算符在两个操作数之后1 2 3 4 5 *无括号运算符按出现顺序处理计算机最爱。较多前缀表达式波兰PN运算符在两个操作数之前 1 2* 3 4 5较少使用。中缀表达式 转 后缀表达式手算方法中缀转后缀的手算方法①确定中缀表达式中的各个运算符的运算顺序运算顺序不唯一因此对应的后缀表达式也不唯一②选择下一个运算符按照【左操作符 右操作符 运算符】的方式组合成一个新的操作数③如果还有运算符没被处理就继续②“左优先”原则只要左边的运算符能先计算就优先算左边的可保证运算顺序唯一后缀表达式的手算方法从左往右扫描每遇到一个运算符就让运算符前面最近的两个操作数执行对应运算合体为一个操作数。注意两个操作数的左右顺序。机算如手算的所示体现出来的特点最后出现的操作数先被运算即后进先出 LIFO后缀表达式的计算机算用栈实现后缀表达式的计算①从左往右扫描下一个元素直到处理完所有元素②若扫描到操作数则压入栈并返回到①否则执行③③若扫描到运算符则弹出两个栈顶元素执行相应的运算运算结果回栈压回栈顶回到①注意后缀表达式的机算先出栈的是“右操作数”如图所示AB运算出结果后则结果回栈压回栈顶。若表达式合法则最后栈中只会留下一个元素其就是最终结果中缀表达式 转 前缀表达式手算方法中缀转前缀的手算方法①确定中缀表达式中的各个运算符的运算顺序运算顺序不唯一因此对应的后缀表达式也不唯一②选择下一个运算符按照【 运算符 左操作符 右操作符 】的方式组合成一个新的操作数③如果还有运算符没被处理就继续②“右优先”原则只要右边的运算符能先计算就优先算右边的可保证运算顺序唯一机算前缀表达式的计算机算用栈实现前缀表达式的计算①从右往左扫描下一个元素直到处理完所有元素②若扫描到操作数则压入栈并返回到①否则执行③③若扫描到运算符则弹出两个栈顶元素执行相应的运算运算结果回栈压回栈顶回到①注意前缀表达式的机算先出栈的是“左操作数”总结下图为手算的运算优先原则。将中缀转后缀时符号运算左优先将后缀转中缀时从左到右也可以理解为左优先但右边是不可行的因为运算符在右边中缀转前缀前缀转中缀同理。机算时后缀先出栈的为右操作数前缀先出栈的为左操作数