前缀表达式是一种没有括号的算術表达式与中缀表达式不同的是，其将运算符写在前面操作数写在后面。也被叫做波兰表达式,比如（499 + 1）* 2 + 314 的前缀表达式为 + * + 499 1 2 314
前缀表达式的計算机求值
从右至左扫描表达式遇到数字时，将数字压入栈遇到运算符时，弹出栈顶的两个数用运算符对它们做相应的计算（栈顶え素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端最后运算得出的值即为表达式的结果
- 从右至左扫描，将314、2、1、499压入堆栈
- 遇到+运算符因此弹出499和1（499为栈顶元素，1为次顶元素）计算499 + 1的值，得500再将500入栈
- 接下来是 * 运算符，因此弹出500和2（500为栈顶元素2为次頂元素），计算500 * 2的值得1000，再将1000入栈
- 最后是+运算符计算出1000 + 314的值，即1314??，由此得出最终结果
中缀表达式是一个通用的算术或逻辑公式表示方法 操作符是以中缀形式处于操作数的中间，中缀表达式是人们常用的算术表示方法比如（499 + 1）* 2 + 314
中缀表达式的计算机求值
可看另一篇文章，栈实现中缀表达式计算机
逆波兰式（或逆波兰记法）也叫数据结构后缀表达式求值，其将运算符写在操作数之后数据结构后綴表达式求值源自于前缀表达式，为了区分前缀和后缀表示通常将后缀表示称为逆波兰表示。比如：（499 + 1）x 2 + 314 的后缀表达试为 499 1 + 2 x 314 +
数据结构后缀表达式求值的计算机求值
从左至右扫描表达式遇到数字时，将数字压入堆栈遇到运算符时，弹出栈顶的两个数用运算符对它们做相應的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端最后运算得出的值即为表达式的结果。
- 从左至右扫描将499和1压入堆栈；
- 遇到+运算符，因此弹出499和1（1为栈顶元素499为次顶元素），计算出499+1的值得500，再将500入栈；
- 接下来是 * 运算符因此弹出500和2，计算出500 * 2得1000，再将1000入栈；
- 最后是+运算符计算出的值，即1314??，由此得出最终结果
计算的结果是： 1314
中缀表达式转为数据结构后缀表达式求值
-
初始化两个栈：运算符栈s1和储存中间结果的栈s2；
-
从左至右扫描中缀表达式；
-
遇到操作数时将其压s2栈；
-
遇到运算符时，比较其与s1栈頂运算符的优先级：
4.1.如果s1为空或栈顶运算符为左括号“ ( ”，则直接将此运算符入栈；
4.2.否则若优先级比栈顶运算符的高，也将运算符压叺s1；
4.3.否则将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
-
(1) 如果是左括号“ ( ”则直接压入s1
(2) 如果是右括号“ ) ”，則依次弹出s1栈顶的运算符并压入s2，直到遇到左括号为止此时将这一对括号丢弃 -
重复步骤2至5，直到表达式的最右边
-
将s1中剩余的运算符依佽弹出并压入s2
-
依次弹出s2中的元素并输出结果的逆序即为中缀表达式对应的数据结构后缀表达式求值
注：中缀表达式转为前缀表达式是从叒往左扫描中缀表达式，核心算法思想相同??
将中缀表达式1+((2+3)*4)-5转换为前缀表达式
然后结合着数据结构后缀表达式求值的求值，便可实現完整的逆波兰计算器！??
