DSA - 表达式解析(Expression Parsing)
编写算术表达式的方法称为notation 。 算术表达式可以用三种不同但等效的符号书写，即不改变表达式的本质或输出。 这些符号是 -
- Infix Notation
- 前缀（波兰语）表示法
- 后缀（反向波兰）表示法
这些符号被命名为它们如何在表达式中使用运算符。 我们将在本章中学到相同的内容。
中缀表示法
我们用中infix表示法编写表达式，例如a - b + c，其中运算符用in操作数之间。 我们人类很容易用中缀符号进行读，写和说话，但同样适用于计算设备。 在时间和空间消耗方面，处理中缀符号的算法可能是困难且昂贵的。
前缀表示法
在这种表示法中，运算符是操作数的prefix ，即操作符在操作数之前写入。 例如， +ab 。 这相当于其中缀符号a + b 。 前缀表示法也称为Polish Notation 。
后缀表示法
这种符号样式称为Reversed Polish Notation 。 在这种表示法样式中，运算符postfix为操作数，即操作符在操作数之后写入。 例如， ab+ 。 这相当于其中缀符号a + b 。
下表简要介绍了所有三种符号的区别 -
| Sr.No. | 中缀表示法 | 前缀表示法 | 后缀表示法 |
|---|---|---|---|
| 1 | a + b | + ab | ab + |
| 2 | （a + b）* c | * + abc | ab + c * |
| 3 | a *（b + c） | * a + bc | abc + * |
| 4 | a/b + c/d | +/ab/cd | ab/cd/+ |
| 5 | （a + b）*（c + d） | * + ab + cd | ab + cd + * |
| 6 | （（a + b）* c） - d | - * + abcd | ab + c * d - |
解析表达式
正如我们已经讨论过的，设计一个解析中缀符号的算法或程序并不是一种非常有效的方法。 相反，这些中缀符号首先转换为后缀或前缀表示法，然后进行计算。
要解析任何算术表达式，我们还需要处理运算符优先级和关联性。
优先级 Precedence
当操作数位于两个不同的运算符之间时，哪个运算符将首先取操作数，由运算符优先于其他运算符决定。 例如 -
由于乘法运算优先于加法，因此将首先计算b * c。 稍后提供运算符优先级表。
结合性 Associativity
关联性描述了具有相同优先级的运算符出现在表达式中的规则。 例如，在表达式a + b -c中，+和 - 具有相同的优先级，然后表达式的哪个部分将首先被评估，由这些运算符的关联性决定。 这里，+和 - 都是左关联的，因此表达式将被评估为(a + b) − c 。
优先级和关联性决定了表达式的评估顺序。 以下是运算符优先级和关联表（从最高到最低） -
| Sr.No. | 操作者 | 优先权 | 关联性 |
|---|---|---|---|
| 1 | Exponentiation ^ | Highest | Right Associative |
| 2 | 乘法（*）和除法（/） | Second Highest | Left Associative |
| 3 | 加法（+）和减法（ - ） | Lowest | Left Associative |
上表显示了运算符的默认行为。 在表达式评估的任何时间点，可以使用括号来更改顺序。 例如 -
在a + b*c ，首先评估表达式部分b * c ，乘法作为加法的优先级。 我们在这里使用括号来首先评估(a + b)*c ，如(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
要查看C编程语言的实现，请单击此处 。
