java公式解析器学习与开发（2）——前缀表达式

1 释义

前缀表达式即 前序表达式。

它是一种不含括号的 算术表达式，特点是将 运算符 写在前面，操作数 写在后面。为纪念其发明者波兰数学家 Jan Lukasiewicz，也称为“波兰式”。例如，- 1 + 2 3 等价于 1-(2+3)。

2 求值方法

对于前缀表达式的求值，需遵循从右至左扫描表达式的原则：

1. 从右边第一个字符开始判断。
2. 如果当前字符是数字，则一直记录到数字串末尾。
3. 如果是 运算符，则将右边离得最近的两个“数字串”作相应运算，以此作为一个新的“数字串”并记录下来。
4. 一直扫描到表达式的最左端，最后运算的值即为表达式的值。

示例： 前缀表达式 - 1 + 2 3 的求值过程：

• 扫描到 3 时，记录数字串 3。
• 扫描到 2 时，记录数字串 2。
• 扫描到 + 时，将 + 右移作为相邻两数字串的 运算符，记为 2+3，结果为 5，记录新数字串 5。
• 继续向左扫描，扫描到 1 时，记录数字串 1。
• 扫描到 - 时，将 - 右移作为相邻两数字串的运算符，记为 1-5，结果为 -4。
• 所以表达式的值为 -4。

3 公式用法

前缀表达式是一种十分有用的表达式，它将中缀表达式转换为可以依靠简单操作就能得到运算结果的表达式。例如，(a+b)*(c+d) 转换为 *,+,a,b,+,c,d。

优势： 只用两种简单的操作（入栈和 出栈）就可以解决任何中缀表达式的运算。

运算方式：

• 如果当前字符（或字符串）为数字或 变量，则压入栈内。
• 如果是 运算符，则将栈顶两个元素弹出栈外并作相应运算，再将结果压入栈内。
• 当前缀表达式扫描结束时，栈里的就是中缀表达式运算的最终结果。

4 相关例子

• a+b ---> +,a,b
• a+(b-c) ---> +,a,-,b,c
• a+(b-c)*d ---> +,a,*,-,b,c,d
• a=1+3 ---> =,a,+,1,3

5 转换算法

将中缀表达式转换为前缀表达式的算法步骤如下：

1. 构造栈：首先构造一个运算符栈（也可放置括号），运算符（以括号分界点）在栈内遵循越往栈顶优先级不降低的原则进行排列。

2. 扫描表达式：从右至左扫描中缀表达式，从右边第一个字符开始判断：

   • 数字：如果当前 字符 是数字，则分析到数字串的结尾并将数字串直接输出。

   • 运算符：如果是运算符，则比较优先级。

     • 如果当前运算符的优先级大于等于栈顶运算符的优先级（当栈顶是括号时，直接入栈），则将运算符直接入栈。
     • 否则，将栈顶运算符 出栈 并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级（当栈顶是括号时，直接入栈），再将当前运算符入栈。

   • 括号：如果是括号，则根据括号的方向进行处理。

     • 如果是右括号 )，则直接入栈。
     • 如果是左括号 (，则遇左括号前将所有的运算符全部 出栈 并输出，遇左括号后将左右的两括号一起删除。
3. 结束处理：重复上述操作直至扫描结束，将栈内剩余运算符全部 出栈 并输出，再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。

6 实例分析

将中缀表达式 1+((2+3)*4)-5 转换为前缀表达式。

7 运算符优先级

• )：直接入栈
• (：遇 ) 前，将运算符全部出栈并输出；遇 ) 后，将两括号一起删除①
• +、-：优先级 1
• *、/、%：优先级 2
• ^：优先级 3