Python 中的逆波兰表示法（RPN）计算器

• 下载 rpn.zip - 741 B

引言

通过本文，我希望演示如何创建一个逆波兰表示法 (RPN) 计算器，它可以用来评估后缀表达式。在后缀表达式中，运算符出现在其操作数之后。例如，像 25 + 12 这样的中缀表达式，在后缀表示法中会被写成 25 12 +。后缀表达式的评估顺序是按照运算出现的顺序进行的（从左到右）。

为此，我们需要定义一个栈类。这个栈类将作为操作数以及中间结果的容器。最终结果也存储在栈中，并在过程结束时提取并显示。

背景

RPN 计算器，也称为堆栈计算器，是一种特殊的计算器，在表达式中，一个运算符之前必须有两个操作数。RPN 计算器通过将操作数压入栈中，直到遇到一个运算符来工作。当遇到一个运算符时，最后压入的两个操作数会被弹出，执行所需的运算，并将运算结果再次压入栈中。在表达式结束时，最后一个值从栈中弹出并显示为最终结果。

Using the Code

以下是 Node 类的代码，它是我们 Stack 类的构建块。它定义了一个构造函数和所需的getter 和 setter 方法。

# Representing the node for the stack.
# The node class defines a constructor and the required getter and setter methods.

class Node:

   def __init__(self,d):
       self.data = d

   def setnext(self,n):
       self.next = n

   def getdata(self):
       return self.data

   def getnext(self):
       return self.next

以下是 Stack 类的代码。它定义了一个构造函数以及 push 和 pop 操作，此外还有一个方法来检查 stack 是否为空。

# Representing the stack class.
# The stack class defines a constructor and the implementations for the
# push and pop operations. It also contains a method to check if the stack is empty.

class Stack:

   def __init__(self):
       self.top = None

   def push(self,d):
       self.newnode = Node(d)
       self.newnode.setnext(self.top)
       self.top = self.newnode

   def pop(self):
       temp = self.top
       self.top = self.top.getnext()
       n = temp.getdata()
       del temp
       return n

   def isempty(self):
       return self.top == None

以下是主程序代码。主程序包括从用户那里接受输入，并使用我们 stack 类的函数执行计算。输入的表达式要被评估，必须在两个操作数之间以及在操作数和运算符之间有一个空格，例如，78 100 + 200 - 5 *

该代码使用正则表达式模块 (re) 的 sub() 函数将后缀表达式中的多个空格替换为单个空格，并使用 split() 函数解析表达式并提取表达式的元素（运算符和操作数）到一个列表中。strip() 函数用于删除前导和尾随空格。它将操作数压入栈中，并在遇到运算符时弹出最后两个操作数并压入它们的计算结果。最后，它从栈中弹出并显示值作为最终结果。

import re

if __name__ == "__main__":
    try:
        mystack = Stack()
        expr = input("Enter expression with space between numbers and operators: ")
        expr = re.sub(" +"," ",expr)
        expr = expr.strip()
        elements = re.split(r"[\s]",expr)
        for x in elements:
            if x == "+":
                n1 = int(mystack.pop())
                n2 = int(mystack.pop())
                n3 = n2 + n1
                mystack.push(n3)
            elif x == "-":
                n1 = int(mystack.pop())
                n2 = int(mystack.pop())
                n3 = n2 - n1
                mystack.push(n3)
            elif x == "*":
                n1 = int(mystack.pop())
                n2 = int(mystack.pop())
                n3 = n2 * n1
                mystack.push(n3)
            elif x == "//":
                n1 = int(mystack.pop())
                n2 = int(mystack.pop())
                n3 = n2 // n1
                mystack.push(n3)
            elif x == "/":
                n1 = int(mystack.pop())
                n2 = int(mystack.pop())
                n3 = n2 / n1
                mystack.push(n3)
            else:
                mystack.push(x)
        print("Result: " + str(mystack.pop()))
    except AttributeError as e:
        print("Invalid Expression: " + str(e))

历史

• 2022 年 11 月 10 日：初始版本