evaluate_reverse_polish_notation

View Source

 1# @leet start
 2class Solution:
 3    def evalRPN(self, tokens: list[str]) -> int:
 4        """
 5        This problem asks to evaluate reverse polish notation.
 6        The way to do this is to use a stack and ops, as you would in a stack VM.
 7        If we encounter a number, we put it onto the top of the stack.
 8        If we encounter an operator, we pop the last two numbers from the stack,
 9        apply the operation, and then put it on top of the stack.
10        At the end, we return the top of the stack.
11        This works because the numbers are preceded by their operation, so
12        they are evaluated just when needed, and never after.
13
14        For infix notation, you'd have to use either recursive descent or pratt
15        parsing to handle this problem, since once you see a `+` or `-` operator,
16        you have to keep parsing until you hit another `+` or `-` operator before
17        you can resolve the current operator.
18        """
19        ops = {
20            "+": lambda a, b: a + b,
21            "-": lambda a, b: a - b,
22            "*": lambda a, b: a * b,
23            "/": lambda a, b: int(a / b),
24        }
25
26        stack = []
27        for token in tokens:
28            if token in ops:
29                top = stack.pop()
30                prev = stack.pop()
31                op = ops[token]
32                stack.append(op(prev, top))
33            else:
34                stack.append(int(token))
35        return stack.pop()
36
37
38# @leet end
39
40
41def test():
42    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def evalRPN(self, tokens: list[str]) -> int:
 5        """
 6        This problem asks to evaluate reverse polish notation.
 7        The way to do this is to use a stack and ops, as you would in a stack VM.
 8        If we encounter a number, we put it onto the top of the stack.
 9        If we encounter an operator, we pop the last two numbers from the stack,
10        apply the operation, and then put it on top of the stack.
11        At the end, we return the top of the stack.
12        This works because the numbers are preceded by their operation, so
13        they are evaluated just when needed, and never after.
14
15        For infix notation, you'd have to use either recursive descent or pratt
16        parsing to handle this problem, since once you see a `+` or `-` operator,
17        you have to keep parsing until you hit another `+` or `-` operator before
18        you can resolve the current operator.
19        """
20        ops = {
21            "+": lambda a, b: a + b,
22            "-": lambda a, b: a - b,
23            "*": lambda a, b: a * b,
24            "/": lambda a, b: int(a / b),
25        }
26
27        stack = []
28        for token in tokens:
29            if token in ops:
30                top = stack.pop()
31                prev = stack.pop()
32                op = ops[token]
33                stack.append(op(prev, top))
34            else:
35                stack.append(int(token))
36        return stack.pop()

def evalRPN(self, tokens: list[str]) -> int: View Source

 4    def evalRPN(self, tokens: list[str]) -> int:
 5        """
 6        This problem asks to evaluate reverse polish notation.
 7        The way to do this is to use a stack and ops, as you would in a stack VM.
 8        If we encounter a number, we put it onto the top of the stack.
 9        If we encounter an operator, we pop the last two numbers from the stack,
10        apply the operation, and then put it on top of the stack.
11        At the end, we return the top of the stack.
12        This works because the numbers are preceded by their operation, so
13        they are evaluated just when needed, and never after.
14
15        For infix notation, you'd have to use either recursive descent or pratt
16        parsing to handle this problem, since once you see a `+` or `-` operator,
17        you have to keep parsing until you hit another `+` or `-` operator before
18        you can resolve the current operator.
19        """
20        ops = {
21            "+": lambda a, b: a + b,
22            "-": lambda a, b: a - b,
23            "*": lambda a, b: a * b,
24            "/": lambda a, b: int(a / b),
25        }
26
27        stack = []
28        for token in tokens:
29            if token in ops:
30                top = stack.pop()
31                prev = stack.pop()
32                op = ops[token]
33                stack.append(op(prev, top))
34            else:
35                stack.append(int(token))
36        return stack.pop()

This problem asks to evaluate reverse polish notation. The way to do this is to use a stack and ops, as you would in a stack VM. If we encounter a number, we put it onto the top of the stack. If we encounter an operator, we pop the last two numbers from the stack, apply the operation, and then put it on top of the stack. At the end, we return the top of the stack. This works because the numbers are preceded by their operation, so they are evaluated just when needed, and never after.

For infix notation, you'd have to use either recursive descent or pratt parsing to handle this problem, since once you see a + or - operator, you have to keep parsing until you hit another + or - operator before you can resolve the current operator.

def test(): View Source

42def test():
43    assert 2 + 2 == 4