数据结构中的前缀和后缀表达式

编写算术表达式的方法称为符号。算术表达式可以用三种不同但等效的符号表示,即,无需更改表达式的本质或输出。这些符号是–

  • 中缀

  • 字首

  • 后缀

缀符号是正常的符号,我们在编写不同的数学表达式时会使用它们。前缀和后缀表示法有很大不同。

前缀符号

在这种表示法中,运算符以操作数为前缀,即运算符被写在操作数之前。例如,+ ab。这等效于其后缀符号a + b。前缀符号也称为波兰符号

后缀符号

这种表示法样式称为反向波兰表示法。在这种表示方式中,运算符后缀到操作数之后,即运算符写在操作数之后。例如,ab +。这等效于其后缀符号a + b

示例

表达式编号中缀符号前缀符号后缀符号
1a + b+ AbAb +
2(a + b)* c* + abcab + c *
3a *(b + c)* a + bcabc + *
4a / b + c / d+ / AB / CDab / cd / +
5(a + b)*(c + d)* + AB + CDab + cd + *
6((a + b)* c)-d-* + abcdab + c * d-

解析表达式

正如我们已经讨论的那样,这不是一种设计算法或程序来解析中缀符号的非常有效的方法。而是将这些infix表示法首先转换为postfix或前缀表示法,然后进行计算。

要解析任何算术表达式,我们还需要注意运算符的优先级和关联性。

优先顺序

当一个操作数位于两个不同的运算符之间时,哪个运算符将最先采用该操作数,取决于一个运算符的优先级。例如 -