Evaluate Reverse Polish Notation

Dạo này đi làm chán quá nên quyết định ngồi code giết thời gian. Chọn leetcode vì những problems trên trang này khá hay (hình như cóp nhặt những câu hỏi hay gặp lúc phỏng vấn), lại hỗ trợ python. Thôi tập luyện tí vừa là xem lại kiến thức thuật toán, vừa cũng cố python vậy.

Evaluate Reverse Polish Notation  (Ký pháp Ba Lan)

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Xem ví dụ thì 13/5 = 2, tức là phải làm tròn phép chia.

Đoạn code sau sử dụng stack.

1:  class Solution:  
2:    # @param tokens, a list of string  
3:    # @return an integer  
4:    def evalRPN(self, tokens):  
5:      stack = []  
6:      for t in tokens:  
7:        if t == '+':  
8:          stack[-2] = stack[-2] + stack[-1]  
9:          stack.pop()  
10:        elif t == '-':  
11:          stack[-2] = stack[-2] - stack[-1]  
12:          stack.pop()  
13:        elif t == '*':  
14:          stack[-2] = stack[-2] * stack[-1]  
15:          stack.pop()  
16:        elif t == '/':  
17:          stack[-2] = int(stack[-2] / float(stack[-1]))  // làm tròn phép chia
18:          stack.pop()  
19:        else:  
20:          stack.append(int(t))  
21:      return stack[-1]