算法：解析表达式算法

编写算术表达式的方法称为符号。算术表达式可以用三种不同但等效的符号书写，即不改变表达式的本质或输出。这些符号是 -

中缀表示法
前缀(波兰语)表示法
后缀(反向波兰)表示法

这些符号被命名为它们如何在表达式中使用运算符。我们将在本章中学到相同的内容。

中缀表示法

我们用中缀表示法编写表达式，例如a - b + c，其中运算符用在操作数之间。我们人类很容易用中缀符号进行读，写和说话，但同样适用于计算设备。在时间和空间消耗方面，处理中缀符号的算法可能是困难且昂贵的。

前缀表示法

在这种表示法中，运算符是操作数的前缀，即操作符在操作数之前写入。例如， + ab 。这相当于其中缀符号 a + b 。前缀表示法也称为 波兰表示法 。

后缀表示法

这种符号样式称为 反转波兰表示法 。在这种表示法样式中，运算符后缀为操作数，即操作符在操作数之后写入。例如， 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 -

解析表达式

正如我们已经讨论过的，设计一个解析中缀符号的算法或程序并不是一种非常有效的方法。相反，这些中缀符号首先转换为后缀或前缀表示法，然后进行计算。

要解析任何算术表达式，我们还需要处理运算符优先级和关联性。

优先权

当操作数位于两个不同的运算符之间时，哪个运算符将首先取操作数，由运算符优先于其他运算符决定。例如 -

运营商优先

由于乘法运算优先于加法，因此将首先计算b * c。稍后提供运算符优先级表。

关联性

关联性描述了具有相同优先级的运算符出现在表达式中的规则。例如，在表达式a + b -c中，+和 - 具有相同的优先级，然后表达式的哪个部分将首先被评估，由这些运算符的关联性决定。这里，+和 - 都是左关联的，因此表达式将被评估为 (a + b) - c 。

优先级和关联性决定了表达式的评估顺序。以下是运算符优先级和关联表(从最高到最低) -

Sr.No.	操作者	优先权	关联性
1	Exponentiation ^	最高	正确联想
2	乘法(*)和除法(/)	第二高	左联想
3	加法(+)和减法( - )	最低	左联想

上表显示了运算符的默认行为。在表达式评估的任何时间点，可以使用括号来更改顺序。例如 -

在 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

下一章：算法：队列算法

队列是一种抽象的数据结构，有点类似于Stacks。与堆栈不同，队列的两端都是开放的。一端始终用于插入数据(入队)，另一端用于删除数据(出队)。队列遵循先进先出方法，即首先访问先存储的数据项。一个真实的队列示例可以是单车道单向 ...

上一章：算法：堆栈算法

下一章：算法：队列算法