栈式虚拟机演示 - 后置运算执行

后缀表达式（Postfix Notation），又称逆波兰表示法（Reverse Polish Notation, RPN），是一种将运算符置于操作数之后的数学表达式书写方式。例如，中缀表达式 3 + 4 在后缀表示法中写作 3 4 +。这种表示法不需要括号来定义运算优先级，计算机可以按照从左到右的顺序高效求值，非常适合栈式虚拟机执行。它由波兰逻辑学家扬·武卡谢维奇于1924年提出。

栈式虚拟机使用一个栈（Stack）来执行后缀表达式：
① 从左到右扫描表达式中的每个token；
② 遇到数字时，将其压入栈中（push）；
③ 遇到运算符时，从栈顶弹出两个操作数（先弹出右操作数，再弹出左操作数），进行计算，然后将结果压回栈中；
④ 扫描结束后，栈中剩下的唯一元素即为最终结果。这种执行方式高效、无歧义，被广泛应用于计算器、编译器和虚拟机实现中。

① 无需括号：后缀表达式天然消除了运算符优先级和括号的需求，表达式更简洁；
② 求值高效：只需一次从左到右的扫描，使用栈即可完成求值，时间复杂度O(n)；
③ 实现简单：栈式虚拟机结构简单，易于硬件实现或在资源受限的环境中运行；
④ 无歧义：每个合法的后缀表达式对应唯一的计算顺序，避免了中缀表达式中运算符优先级的潜在混淆。这也是为什么许多编程语言的字节码采用栈式虚拟机架构（如JVM、Python字节码等）。

使用调度场算法（Shunting Yard Algorithm），由Edsger Dijkstra发明：
① 初始化一个输出队列和一个运算符栈；
② 从左到右扫描中缀表达式的每个token；
③ 遇到数字直接放入输出队列；
④ 遇到运算符时，将其与运算符栈顶比较优先级，若栈顶优先级不低于当前运算符，则弹出栈顶到输出队列，重复此过程后将当前运算符压栈；
⑤ 遇到左括号直接压栈，遇到右括号则不断弹出栈顶到输出队列直到遇到左括号；
⑥ 扫描结束后将栈中剩余运算符全部弹出到输出队列。输出队列中的内容即为后缀表达式。

栈式虚拟机广泛应用于：
① Java虚拟机（JVM）：字节码执行基于操作数栈；
② Python解释器：CPython的字节码虚拟机使用栈式架构；
③ PostScript：Adobe的页面描述语言完全基于后缀表达式和栈操作；
④ Forth语言：经典的栈式编程语言，广泛应用于嵌入式系统；
⑤ 科学计算器：如HP计算器的RPN输入模式；
⑥ 表达式求值引擎：各类需要动态计算数学表达式的系统。

支持的运算符：+（加）、-（减）、*（乘）、/（除）、%（取模）、^（幂运算）。
注意事项：
① 表达式中的token用空格分隔，如 3 4 + 2 *；
② 支持整数和浮点数（如 3.5 2.1 +）；
③ 除法时若除数为0会提示错误；
④ 表达式结束时栈中应恰有1个元素（最终结果），多余或不足都说明表达式有误；
⑤ 运算符出现时必须保证栈中至少有2个操作数。