后缀表达式求值算法的介绍

动力节点小编告诉大家，在 Postfix 表达式中，运算符写在它们的操作数之后。例如，给出的表达式采用后缀符号 ABC + * D /。

考虑点

允许的操作数：A、B、C、D 表示允许任何实数。

允许的运算符：+、-、*、/、^(取幂)

表达式中允许有空格

括号是允许的

与中缀表达式相比，前缀和后缀表达式的计算速度更快，因为我们不需要处理任何括号或遵循运算符优先规则。在后缀和前缀表达式中，无论其优先级如何，先计算前面的运算符。此外，这些表达式中没有括号。只要我们可以保证使用了有效的前缀或后缀表达式，就可以对其进行正确评估。

评估后缀表达式的算法

第 1 步：如果字符是操作数，则将其压入堆栈

第 2 步：如果字符是运算符，则从堆栈中弹出两个元素。根据运算符对这些元素进行操作，并将结果推回堆栈

第 3 步：将重复第 1 步和第 2 步，直到结束。

第 4 步：结果存储在Java堆栈顶部，返回

第 5 步：结束

后缀评估的复杂性

Postfix 评估算法具有线性复杂度 O(N)。由于我们扫描表达式一次并执行需要恒定时间的推送和弹出操作。