逆波兰表达式求解计算器

利用逆波兰表达式求解计算器有以下几个步骤:

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 0
        elif operator in '*/':
            return 1
        else:
            return -1

    def 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 li

    def infix_to_suffix(self, infix_list):
        result = []
        operator_stack = []

        # check each element
        for 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 result

    def 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)
                break
            else:
                # get the priority of stack top
                top_level = 0
                if stack_top in '+-':
                    top_level = 1
                else:
                    top_level = 2

                if top_level >= level:
                    res.append(stack_top)
                else:
                    operator_stack.append(stack_top)
                    break

        operator_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 == '(':
                break
            else:
                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"))