Chương trình đánh giá biểu thức s dưới dạng chuỗi trong Python

Giả sử chúng ta có một chuỗi s là biểu thức S. Chúng ta phải đánh giá biểu thức S đó và kết quả trả về là số nguyên. Như chúng ta biết rằng biểu thức s là một biểu thức hoặc là một số hoặc biểu thức đệ quy được bao bọc trong dấu ngoặc đơn như (+ (- 3 2) (* 3 3)), cho biết (3 - 2) + (3 * 3) =10. Các toán tử hợp lệ ở đây là +, -, * và /.

Vì vậy, nếu đầu vào là s =​​"(- (+ 3 2) 2)", thì đầu ra sẽ là 3, là ((3 + 2) - 2) =3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• stack:=một ngăn xếp mới

• bỏ dấu ngoặc mở và đóng ngoặc đơn của s

• a:=split s sử dụng dấu cách và tạo danh sách các phân vùng

• đối với mỗi i theo thứ tự ngược lại, hãy thực hiện

  • nếu kích thước của i> 1, thì

    • nếu tôi [0] giống với "-" thì

      • đẩy tôi dưới dạng số nguyên vào ngăn xếp

      • chuyển sang lần lặp tiếp theo

    • nếu không,

      • đẩy tôi dưới dạng số nguyên vào ngăn xếp

  • ngược lại khi tôi là một chữ số thì

    • đẩy tôi dưới dạng số nguyên vào ngăn xếp

  • nếu không,

    • nếu kích thước của ngăn xếp> =2, thì

      • num1:=pop từ ngăn xếp

      • num2:=pop from stack

      • nếu tôi giống với "+", thì

        • thực hiện num1 + num2 và đẩy vào ngăn xếp

      • ngược lại khi tôi giống với "-" thì

        • thực hiện num1 - num2 và đẩy vào ngăn xếp

      • ngược lại khi tôi giống với "*" thì

        • thực hiện num1 * num2 và đẩy vào ngăn xếp

      • nếu không,

        • thực hiện num1 / num2 và đẩy vào ngăn xếp

• trả về phần tử trên cùng từ ngăn xếp và xóa phần tử trên cùng

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class Solution:
   def solve(self, s):
      stack = list()
      s = s.replace("(", "")
      s = s.replace(")", "")
      a = s.split()
      for i in a[::-1]:
         if len(i) > 1:
            if i[0] == "-":
               stack.append(int(i))
               continue
            else:
               stack.append(int(i))
         elif i.isdigit():
            stack.append(int(i))
         else:
            if len(stack) >= 2:
               num1 = stack.pop()
               num2 = stack.pop()
               if i == "+":
                  stack.append(int(num1 + num2))
               elif i == "-":
                  stack.append(int(num1 - num2))
               elif i == "*":
                  stack.append(int(num1 * num2))
               else:
                  stack.append(int(num1 / num2))
      return stack.pop()
ob = Solution()
s = "(- (+ 3 2) 2)"
print(ob.solve(s))

Đầu vào

s = "(- (+ 3 2) 2)"

Đầu ra

3