数据结构中的前缀和后缀表达式
编写算术表达式的方法称为符号。算术表达式可以用三种不同但等效的符号表示,即,无需更改表达式的本质或输出。这些符号是–
中缀
字首
后缀
缀符号是正常的符号,我们在编写不同的数学表达式时会使用它们。前缀和后缀表示法有很大不同。
前缀符号
在这种表示法中,运算符以操作数为前缀,即运算符被写在操作数之前。例如,+ab。这等效于其后缀符号a+b。前缀符号也称为波兰符号。
后缀符号
这种表示法样式称为反向波兰表示法。在这种表示方式中,运算符后缀到操作数之后,即运算符写在操作数之后。例如,ab+。这等效于其后缀符号a+b。
示例
解析表达式
正如我们已经讨论的那样,这不是一种设计算法或程序来解析中缀符号的非常有效的方法。而是将这些infix表示法首先转换为postfix或前缀表示法,然后进行计算。
要解析任何算术表达式,我们还需要注意运算符的优先级和关联性。
优先顺序
当一个操作数位于两个不同的运算符之间时,哪个运算符将最先采用该操作数,取决于一个运算符的优先级。例如-