Calculator

Template

772. Basic Calculator III

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

• Operand has 2 level priority

• l2 prior than l1, o1 denotes (+, -), o2 denotes (*, /)

• sign can happen in the beginning of string

• Conditions

  • 1 Numbers: get the number, update l2 and sign

  • 2 (*, /) operator: update o2

  • 3 (+, /) operator: update l1, o1, reset l2, o2

  • 4 '(': Use recursion to find num and update l2

  • Hint: ignore ')'

• final return l1 + o1*l2

Recursion

def calculate(self, s: str) -> int:
    s.replace(' ', '')
    l1, o1 = 0, 1
    l2, o2 = 1, 1
    sign = 0
    
    i = 0
    if s[0] in ('+', '-'):
        sign = 1 if s[0] == '+' else -1
        i+=1
    
    # must ignore ')'    
    while i < len(s):
        c = s[i]
        if c.isdigit():
            num = int(c)
            while i+1 < len(s) and s[i+1].isdigit():
                num = num*10 + int(s[i+1])
                i+=1               
            if sign:
                num *= sign                   
            l2 = l2*num if o2 else int(l2/num)
            sign = 0
            
        elif c == '(':
            count = 0
            start = i
            while i < len(s):
                if s[i] == '(': count+=1
                if s[i] == ')': count-=1
                if count == 0: break
                i+=1
            
            num = self.calculate(s[start+1:i])
            l2 = l2*num if o2 else int(l2/num)
            
        elif c in ('*', '/'):
            o2 = 1 if c == '*' else 0
            
        elif c in ('+', '-'):
            l1 = l1 + o1*l2
            o1 = 1 if c == '+' else -1
            l2, o2 = 1, 1                
        i+=1   
        
    return l1 + o1*l2           

Stack

public int calculate(String s) {
    int l1 = 0, o1 = 1;
    int l2 = 1, o2 = 1;
    Stack<Integer> stack = new Stack<>();

    for(int i=0; i<s.length(); i++){
        char c = s.charAt(i);
        if(Character.isDigit(c)){
            int num = c - '0';
            while(i+1 < s.length() && Character.isDigit(s.charAt(i+1)))
                num = num*10 + s.charAt(++i) - '0';
            l2 = (o2 == 1 ? l2*num : l2/num); 

        }else if(c == '('){
            // preserve l1, o1, l2, o2
            stack.push(l1);
            stack.push(o1);
            stack.push(l2);
            stack.push(o2);

            l1 = 0; o1 = 1;
            l2 = 1; o2 = 1;

        }else if(c == ')'){
            // caculate current num
            int num = l1 + o1*l2;

            // get old status;
            o2 = stack.pop();
            l2 = stack.pop();
            o1 = stack.pop();
            l1 = stack.pop();

            l2 = (o2 == 1 ? l2*num : l2/num);

        }else if(c == '*' || c == '/'){
            o2 = c == '*' ? 1 : -1;

        }else if(c == '+' || c == '-'){
            l1 = l1 + o1*l2;
            o1 = c == '+'? 1 : -1;
            l2 = 1;
            o2 = 1;
        }
    }
    return l1 + o1*l2;
}

224. Basic Calculator I

+, - , (, )

def calculate(self, s: str) -> int: s.replace(' ', '')
    l, o = 0, 1
    i=0

    while i < len(s):
        c = s[i]
        if c.isdigit():
            num = int(s[i])
            while i+1 < len(s) and s[i+1].isdigit():
                num = num*10 + int(s[i+1])
                i+=1    
            l = l+num if o else l-num

        elif c == '(':
            start = i
            count = 0
            while i < len(s):
                if s[i] == '(': count += 1
                elif s[i] == ')': count -= 1
                if count == 0: break
                i+=1

            num = self.calculate(s[start+1:i])
            l = l+num if o else l-num

        elif c in ('+', '-'):
            o = 1 if c == '+' else 0  
        i+=1

    return l

Stack

def calculate(self, s: str) -> int:
    s.replace(' ', '')
    l, o = 0, 1
    i=0

    stack = []

    while i < len(s):
        c = s[i]
        if c.isdigit():
            num = int(s[i])
            while i+1 < len(s) and s[i+1].isdigit():
                num = num*10 + int(s[i+1])
                i+=1    
            l = l+num if o else l-num

        elif c == '(':
            stack.append(o)
            stack.append(l)
            l, o = 0, 1

        elif c == ')':
            l_pre = stack.pop()
            o_pre = stack.pop()

            l = l_pre+l if o_pre else l_pre-l

        elif c in ('+', '-'):
            o = 1 if c == '+' else 0  
        i+=1

    return l

227. Calculator II

+, - *, /

def calculate(self, s: str) -> int:
    n1, o1 = 0, 1
    n2, o2 = 1, 1
    
    i = 0
    while i<len(s):
        c = s[i]
        if c.isdigit():
            num = int(c)
            while i+1 < len(s) and s[i+1].isdigit():
                num = num*10 + int(s[i+1])
                i+=1
            n2 = n2*num if o2 else n2//num
        elif c in ('*', '/'):
            o2 = 1 if c == '*' else 0
        elif c in ('+', '-'):
            n1 = n1 + o1*n2
            o1 = 1 if c == '+' else -1
            n2 = 1
            o2 = 1
        i+=1
            
    return n1+o1*n2