Data Structures Algorithms 简明教程

Expression Parsing in Data Structure

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

An expression is any word or group of words or symbols that generates a value on evaluation. Parsing expression means analyzing the expression for its words or symbols depending on a particular criterion. Expression parsing is a term used in a programming language to evaluate arithmetic and logical expressions.

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

The way to write arithmetic expression is known as a notation. An arithmetic expression can be written in three different but equivalent notations, i.e., without changing the essence or output of an expression. These notations are −

  1. Infix Notation

  2. Prefix (Polish) Notation

  3. Postfix (Reverse-Polish) Notation

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

These notations are named as how they use operator in expression. We shall learn the same here in this chapter.

Infix Notation

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

We write expression in infix notation, e.g. a - b + c, where operators are used in-between operands. It is easy for us humans to read, write, and speak in infix notation but the same does not go well with computing devices. An algorithm to process infix notation could be difficult and costly in terms of time and space consumption.

Prefix Notation

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

In this notation, operator is prefix*ed to operands, i.e. operator is written ahead of operands. For example, *+ab. This is equivalent to its infix notation a + b. Prefix notation is also known as 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 。

This notation style is known as Reversed Polish Notation. In this notation style, the operator is postfix*ed to the operands i.e., the operator is written after the operands. For example, *ab+. This is equivalent to its infix notation a + b.

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

The following table briefly tries to show the difference in all three notations −

Parsing Expressions

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

As we have discussed, it is not a very efficient way to design an algorithm or program to parse infix notations. Instead, these infix notations are first converted into either postfix or prefix notations and then computed.

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

To parse any arithmetic expression, we need to take care of operator precedence and associativity also.

Precedence

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

When an operand is in between two different operators, which operator will take the operand first, is decided by the precedence of an operator over others. For example −

operator precedence

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

As multiplication operation has precedence over addition, b * c will be evaluated first. A table of operator precedence is provided later.

Associativity

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

Associativity describes the rule where operators with the same precedence appear in an expression. For example, in expression a + b − c, both + and − have the same precedence, then which part of the expression will be evaluated first, is determined by associativity of those operators. Here, both + and − are left associative, so the expression will be evaluated as (a + b) − c.

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

Precedence and associativity determines the order of evaluation of an expression. Following is an operator precedence and associativity table (highest to lowest) −

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

The above table shows the default behavior of operators. At any point of time in expression evaluation, the order can be altered by using parenthesis. For example −

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

In a + b*c, the expression part b*c will be evaluated first, with multiplication as precedence over addition. We here use parenthesis for a + b to be evaluated first, like (a + b)*c.

Postfix Evaluation Algorithm

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

We shall now look at the algorithm on how to evaluate postfix notation −

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

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

Following are the complete implementations of Expression Parsing (Conversion from infix notations to postfix notations) in various programming languages −

Expression Parsing Using Stack

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

We can use different data structures to implement expression parsing. Check the implementation of Expression Parsing using Stack