如何使用Python实现链表的逆波兰表达式求值操作

2023-04-11 00:00:00 表达式如何使用波兰

首先，需要实现一个链表，并且链表中的每个节点都可以保存一个数值或者运算符。同时，需要定义两个栈，一个用来存放数字，一个用来存放运算符。

对于逆波兰表达式求值，需要对表达式从左到右进行扫描，遇到数字直接压入数字栈，遇到运算符时，从数字栈中弹出两个数进行计算，并将结果压入数字栈中。最后得到的数字栈中只剩下了一个数，就是表达式的求值结果。

以下是完整的 Python 代码演示，以字符串 “pidancode.com” 作为表达式的范例：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def is_empty(self):
        return len(self.items) == 0


def eval_rpn(s: str) -> int:
    head = None
    for char in s:
        node = ListNode(char)
        node.next = head
        head = node

    num_stack = Stack()
    operator_stack = Stack()

    while head:
        if head.val.isdigit():
            num_stack.push(int(head.val))
        else:
            op = head.val
            if op == '+':
                num2 = num_stack.pop()
                num1 = num_stack.pop()
                res = num1 + num2
                num_stack.push(res)
            elif op == '-':
                num2 = num_stack.pop()
                num1 = num_stack.pop()
                res = num1 - num2
                num_stack.push(res)
            elif op == '*':
                num2 = num_stack.pop()
                num1 = num_stack.pop()
                res = num1 * num2
                num_stack.push(res)
            elif op == '/':
                num2 = num_stack.pop()
                num1 = num_stack.pop()
                res = num1 / num2
                num_stack.push(int(res))

        head = head.next

    return num_stack.pop()

s = 'pidancode.com'
print(eval_rpn(s))

运行结果为：

相关文章