表达式转换

中缀转前缀

假设有一个中缀表达式 1+((2+3)*4)-5

使用双栈法，首先构造操作数栈和运算符栈（这两个栈不能以字面意思理解，后期会混放，运算符栈属于临时的），然后从右至左扫描中缀表达式。

如果扫描是操作数则直接压入操作数栈；如果扫描是运算符， 是右括号直接放入，是左括号那就把运算符栈中右括号到栈顶的 元素弹出，压入操作数栈。如果是别的运算符就需要比较优先级： 若运算符优先级大于等于栈顶元素，则入栈，否则栈内元素出栈 压入操作数栈。

最后若运算符栈还有元素，那就再弹出压入操作数栈，之后将操作数栈翻转便是转化成为前缀表达式。

中缀转前缀转换图解

中缀转换后缀

假设有一中缀表达式 1 + (( 2 + 3)* 4 ) – 5

采用双栈法，构造一个操作数栈和运算符栈，从左往右遍历中缀表达式，当读到操作数时直接放入操作数栈。当读到运算符时，运算符栈顶元素为空，直接放入。如果运算符是“(”，直接压入栈中，如果运算符是“)”,那就将栈元素弹出压入操作数栈。否则比较优先级，若栈顶元素优先级低，直接入栈；否则就把栈顶元素弹出压入操作数栈，直到遇见栈顶元素优先级低的，然后该元素才能压入运算符栈。中缀表达式读取完后，将运算符栈中的元素压入操作数栈。

中缀转后缀转换图解

表达式求值

前缀与后缀计算区别

前缀表达式求值算法简单描述

前缀表达式只用了一个栈（我称为操作数栈），首先从右向左扫描。遇到操作数直接入栈；遇到运算符，按翻转的顺序（与后缀表达式相反的顺序）出栈计算，然后结果入栈。按照以上规则，扫描完成后，操作数栈中唯一一个数字即为结果。

前缀表达式求值图解

中缀表达式求值算法简单描述

采用双栈法，首先构建两个栈，从左向右扫描，如果扫描到数字，直接放入操作数栈；如果扫描到运算符，运算符栈为空直接放入，否则比较优先级，栈顶优先级高，需要出栈计算：操作数按顺序出栈，运算符出栈，进行计算，将结果放入操作数栈， 之前的运算符入栈。按照以上规则一直扫描完，然后去看运算符栈中是否有运算符，有的话出栈操作，即可得到结果。

彩蛋骰子博客欢迎来踩！https://touzi.bid/?

中缀表示式求值图解

后缀表达式求值算法简单描述

首先设置一个操作数栈，从左往右扫描整个后缀表达式。如果是操作数，则将操作数压入栈中；如果是运算符，则从栈中弹出对应的操作数，根据操作数进行运算并将结果压入栈中；扫描完毕后，操作数栈中仅有一个元素，即为结果。

后缀表达式求值图解