表达式解析
算术表达式的写法称为
记法。算术表达式可以用三种不同但等效的符号来编写，即，不改变表达式的本质或输出。这些符号是-
Infix 符号
Prefix（Polish）符号
Postfix（Reverse-Polish）符号
这些符号被命名为它们如何在表达式中使用运算符。我们将在本章中学习相同的内容。
Infix符号
我们用
infix 表示法写表达式，例如a-b + c，其中运算符在操作数之间使用
in。我们人类很容易以中缀表示法阅读、写作和说话，但计算设备并不顺利。处理中缀符号的算法在时间和空间消耗方面可能是困难和昂贵的。
Prefix符号
在这种表示法中，操作符是操作数的
前缀，即操作符写在操作数之前。例如，
+ab。这相当于它的中缀符号
a + b。前缀表示法也称为
Polish Notation。
Postfix符号
这种表示法风格称为
逆波兰表示法。在这种表示法样式中，操作符被
后缀添加到操作数，即操作符写在操作数之后。例如，
ab+。这相当于它的中缀符号
a + b。
下表简要说明了所有三种符号的区别-
| Infix |
Prefix |
Postfix |
| a + b |
+ a b |
a b + |
| (a + b) * c |
* + a b c |
a b + c * |
| a * (b + c) |
* a + b c |
a b c + * |
| a/b + c/d |
+/a b/c d |
a b/c d/+ |
| (a + b) * (c + d) |
* + a b + c d |
a b + c d + * |
| ((a + b) * c)-d |
-* + a b c d |
a b + c * d- |
解析表达式
正如我们所讨论的，设计一个算法或程序来解析中缀符号并不是一种非常有效的方法。相反，这些中缀表示法首先转换为后缀或前缀表示法，然后进行计算。
要解析任何算术表达式，我们还需要注意运算符优先级和关联性。
优先级
当一个操作数在两个不同的运算符之间时，哪个运算符将首先获取该操作数，这取决于一个运算符的优先级。例如-
由于乘法运算优先于加法运算，因此首先计算 b * c。稍后提供运算符优先级表。
关联性
关联性描述了具有相同优先级的运算符出现在表达式中的规则。例如，在表达式 a + b − c 中，+ 和 – 具有相同的优先级，那么表达式的哪一部分将首先被计算，由这些运算符的关联性决定。在这里，+ 和-都是左关联的，因此表达式将被计算为
(a + b)-c。
优先级和关联性决定了表达式的计算顺序。以下是运算符优先级和关联性表（从高到低）-
| 运算符 |
优先级 |
关联性 |
| 求幂^ |
最高 |
右结合 |
| 乘法（*）和除法（/） |
第二高 |
左联想 |
| 加法（+）和减法（-） |
最低 |
左联想 |
上表显示了运算符的默认行为。在表达式评估的任何时间点，都可以使用括号更改顺序。例如-
在
a + b*c 中，表达式部分
b*
c 将首先被计算，乘法优先于加法。我们在这里使用括号来首先评估
a + b，例如
(a + b)*c。
后缀评估算法
我们现在来看看如何评估后缀符号的算法-
Step 1 − scan the expression from left to right
Step 2 − if it is an operand push it to stack
Step 3 − if it is an operator pull operand from stack and perform operation
Step 4 − store the output of step 3, back to stack
Step 5 − scan the expression until all operands are consumed
Step 6 − pop the stack and perform operation
