My solution posted on LeetCode

Following is a copy & paste from the above link.

This solution works for all similar Calculator questions without extra modification:

1. Basic Calculator
2. Basic Calculator II
3. Basic Calculator III

These questions all ask us to evaluate an infix expression with simple math operators in it. Whats infix? For infix expression(the one we use daily) binary operators appear between two operands. For postfix, the operator appears after the operand, even for unary operand.

Infix: 1 - (1 + 2) Postfix: 1 1 2 + -

Evaluating postfix expressions is much easier and simpler than infix ones, so the general idea is to convert an infix expression to a postfix one, and evaluate the postfix expression with the help of a stack.

The general solution comes in two parts:

1. Transform infix to postfix expression
2. Evaluate postfix expression

1. Transform

Here is the algorithm I found online:

• https://www.andrew.cmu.edu/course/15-200/s06/applications/ln/junk.html
• https://condor.depaul.edu/ichu/csc415/notes/notes9/Infix.htm

def transform(self, s):
    # The generated postfix expression of s
    output = []
    # Wrap `s` with '(' and ')' to make processing easier
    s = s + ')'
    stack = ['(']
    prevC = '('

    hasNum = False
    num = 0
    for c in s:
        if c == ' ':
            continue

        # c is part of number
        if c.isdigit():
            hasNum = True
            num = num * 10 + int(c)
            prevC = c
            continue
        # c is operator
        if hasNum:
            hasNum = False
            output.append(num)
            num = 0

        # check if is negative unary operator
        if c == '-' and (prevC == '(' or prevC in self.operators):
            c = 'neg'
        
        # Pop until '('
        while self.precedence_stack[stack[-1]] >= self.precedence_input[c]:
            popped = stack.pop()
            if popped != '(':
                output.append(popped)
            else:
                break
        # push input on to the stack
        if c != ')':
            stack.append(c)

        prevC = c
    
    return output

2. Evaluate

def evaluate_postfix(self, postfix):
    stack = []

    for each in postfix:
        # Is number
        if each not in self.precedence_input:
            stack.append(each)
            continue

        # Is operator
        if each == '+':
            stack.append(stack.pop() + stack.pop())
        elif each == '-':
            a, b = stack.pop(), stack.pop()
            stack.append(b - a)
        elif each == '*':
            stack.append(stack.pop() * stack.pop())
        elif each == '/':
            a, b = stack.pop(), stack.pop()
            stack.append(int(b / a)) # truncate towards zero
        elif each == 'neg':
            stack.append(-stack.pop())

    return stack[0]

Full Code

class Solution:
    precedence_stack = {
        '(': 0,
        '+': 2,
        '-': 2,
        '*': 4,
        '/': 4,
        'neg': 5,
    }

    precedence_input = {
        '(': 6,
        ')': 0,
        '+': 1,
        '-': 1,
        '*': 3,
        '/': 3,
        'neg': 5,
    }

    operators = set("+-*/")

    def transform(self, s):
        # The generated postfix expression of s
        output = []
        # Wrap `s` with '(' and ')' to make processing easier
        s = s + ')'
        stack = ['(']
        prevC = '('

        hasNum = False
        num = 0
        for c in s:
            if c == ' ':
                continue

            # c is part of number
            if c.isdigit():
                hasNum = True
                num = num * 10 + int(c)
                prevC = c
                continue
            # c is operator
            if hasNum:
                hasNum = False
                output.append(num)
                num = 0

            # check if is negative unary operator
            if c == '-' and (prevC == '(' or prevC in self.operators):
                c = 'neg'
            
            # Pop until '('
            while self.precedence_stack[stack[-1]] >= self.precedence_input[c]:
                popped = stack.pop()
                if popped != '(':
                    output.append(popped)
                else:
                    break
            # push input on to the stack
            if c != ')':
                stack.append(c)

            prevC = c
        
        return output

    def evaluate_postfix(self, postfix):
        stack = []

        for each in postfix:
            # Is number
            if each not in self.precedence_input:
                stack.append(each)
                continue

            # Is operator
            if each == '+':
                stack.append(stack.pop() + stack.pop())
            elif each == '-':
                a, b = stack.pop(), stack.pop()
                stack.append(b - a)
            elif each == '*':
                stack.append(stack.pop() * stack.pop())
            elif each == '/':
                a, b = stack.pop(), stack.pop()
                stack.append(int(b / a)) # truncate towards zero
            elif each == 'neg':
                stack.append(-stack.pop())

        return stack[0]

    def calculate(self, s):
        postfix = self.transform(s)
        return self.evaluate_postfix(postfix)

I am not sure about the time complexity, I think it should be O(n) because we go through the input once, and in the worst case we have to go through the stack once too to pop all the operators in it.