Data Structures Algorithms 简明教程

Expression Parsing in Data Structure

表达式是在求值时生成值的任何单词或一组单词或符号。解析表达式意味着根据特定标准分析表达式的单词或符号。表达式解析是一个在编程语言中用于计算算术和逻辑表达式的术语。

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

  1. Infix Notation

  2. Prefix (Polish) Notation

  3. Postfix (Reverse-Polish) Notation

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

Infix Notation

我们在 infix 符号中编写表达式，例如 a - b + c，其中运算符用于在操作数之间 in 。对于我们人类来说，阅读、编写和用中缀表示法说话很容易，但对于计算设备来说却并非如此。处理中缀表示法的算法在时间和空间消耗方面可能既困难又昂贵。

Prefix Notation

在此表示法中，运算符是 prefix*ed to operands, i.e. operator is written ahead of operands. For example, *+ab 。这等同于它的中缀表示法 a + b 。前缀表示法也称为 Polish Notation 。

Postfix Notation

这种符号样式称为 Reversed Polish Notation 。在这种符号样式中，运算符是 postfix*ed to the operands i.e., the operator is written after the operands. For example, *ab+ 。这等同于它的中缀表示法 a + b 。

下表简要尝试显示所有三种符号之间的差异 −

Parsing Expressions

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

为了解析任何算术表达式，我们还需要注意运算符的优先级和结合性。

Precedence

当一个操作数位于两个不同的运算符之间时，首先取得操作数的运算符是由一个运算符对另一个运算符的优先级决定的。例如 −

operator precedence

由于乘法运算优先级高于加法，因此 b * c 将首先得到评估。运算符优先级表将在后面提供。

Associativity

结合性描述了具有相同优先级的运算符出现在表达式中的规则。例如，在表达式 a + b − c 中，+ 和 - 具有相同的优先级，那么表达式的哪一部分将首先得到评估，由这些运算符的结合性决定。此处，+ 和 - 都是左结合的，因此该表达式的评估结果为 (a + b) − c 。

优先级和结合性决定了表达式求值顺序。以下是运算符优先级和结合性表（从最高到最低）-

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

在 a + b*c 中，表达式部分 b * c 将首先得到评估，其中乘法的优先级高于加法。我们在这里使用括号来使 a + b 首先得到评估，例如 (a + b)*c 。

Postfix Evaluation Algorithm

现在，我们将研究如何评估后缀表示法的算法 −

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

Expression Parsing - Complete implementation

以下是各种编程语言中表达式解析的完整实现（从前缀表示法转换为后缀表示法） −

Expression Parsing Using Stack

我们可以使用不同的数据结构来实现表达式解析。检查 Expression Parsing using Stack 的实现