logo图片
数据结构与算法

表达式解析

算术表达式的写法称为 记法。算术表达式可以用三种不同但等效的符号来编写,即,不改变表达式的本质或输出。这些符号是-
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
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4