利用逆波蘭表達式求解計算器有以下幾個步驟:

1. 去掉字符串中的空格

s = s.replaceAll(" ", "")

2. 講字符串轉換為中序表達式數組

def string_to_infixlist(s):ans = []keep_num = ""for i in range(len(s)):if s[i].isdigit():if i < len(s)-1 and s[i+1].isdigit():keep_num += s[i]else:ans.append(keep_num)keep_num = ""else:ans.append(s[i])return ans

3. 中序表達式數組變后綴表達式數組

從左到右讀取，分以下幾種情況

3.1 遇到操作數，復制到后綴表達式數組

3.2 遇到’(',講字符壓入棧中

3.3 遇到’)‘,從棧中一直彈出符號到后綴表達式，直到遇到’(’

3.4 遇到 ±*/等操作符，此時分為兩種情況

3.4.1 如果棧頂優先級大于或等于當前的操作符，則需要一直彈出棧中的操作符，直到發現優先級更低的元素或者棧為空

3.4.2 棧頂的優先級小于當前元素的優先級(坐括號優先級最低)，則直接將該元素壓入棧中

class Solution:def calculate(self, s):s.replace(" ", "")infix = self.expressionToList(s)return self.infix_to_suffix(infix)def get_priority(self, operator):if operator in '+-':return 0elif operator in '*/':return 1else:return -1def expressionToList(self, s):li = []len_s = len(s)keep_num = ""for i in range(len(s)):if s[i].isdigit():if i != len_s - 1 and s[i+1].isdigit():keep_num += s[i]else:keep_num += s[i]li.append(keep_num)keep_num = ""else:li.append(s[i])return lidef infix_to_suffix(self, infix_list):result = []operator_stack = []# check each elementfor i in range(len(infix_list)):ele = infix_list[i]if ele == '(':operator_stack.append(ele)elif ele == ')':self.do_right_braket(operator_stack, result)elif ele in '+-':self.do_operation(result, operator_stack, ele, 1)elif ele in '*/':self.do_operation(result, operator_stack, ele, 2)else:result.append(ele)while len(operator_stack) > 0:result.append(operator_stack.pop())return resultdef is_opeator(self, element):return element in "+-*/()"def do_operation(self, res, operator_stack, cur, level):while len(operator_stack) > 0:stack_top = operator_stack.pop()if stack_top == '(':operator_stack.append(stack_top)breakelse:# get the priority of stack toptop_level = 0if stack_top in '+-':top_level = 1else:top_level = 2if top_level >= level:res.append(stack_top)else:operator_stack.append(stack_top)breakoperator_stack.append(cur)def do_right_braket(self, stack, res):# pop from stack and push into the result utili met with (while len(stack) > 0:top_ele = stack.pop()if top_ele == '(':breakelse:res.append(top_ele)
# 367*2-23*++# 32+5/78+4*5--
# "3+(6*7-2)+2*3"
# ['3', '2', '+', '5', '/', '7', '8', '+', '4', '*', '5', '-', '-']# ['3', '6', '7', '*', '2', '-', '+', '2', '3', '*', '+']
# correct 367*2-+23*+
print(Solution().calculate("3+(6*7-2)+2*3"))