Problem

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Examples

Example 1:

1
2
3
4

Input:
s = "3+2*2"
Output:
 7

Example 2:

1
2
3
4

Input:
s = " 3/2 "
Output:
 1

Example 3:

1
2
3
4

Input:
s = " 3+5 / 2 "
Output:
 5

Constraints

  • 1 <= s.length <= 3 * 10^5
  • s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
  • s represents a valid expression.
  • All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].
  • The answer is guaranteed to fit in a 32-bit integer.

Solution

Method 1 - Using Stack for Operands 🥈

If all operators had the same priority, we could sequentially calculate each number and operator, saving only the latest result. However, to account for operator priorities (’*’ and ‘/’ having higher priority than ‘+’ and ‘-’), we utilise a stack to track encountered numbers.

A straightforward algorithm is:

  1. Use global variables: prevOpr to remember the last operator encountered, num for the current number, and a stack to hold numbers.
  2. Traverse the string character by character following these rules:
    • If the current character is a blank, simply move to the next step.
    • If it’s a digit, build the number using a while loop to capture the full digit sequence.
    • Otherwise, it’s an operator, indicating completion of a new number (or the end of the string). Process the number with prevOpr based on these rules:
      • If prevOpr is ‘+’ or ‘-’, we may encounter operator with higher priority in the future, so append num or -num to the stack: 
        1
2
3
4
5
6

                  case '+':
              stack.push(num);
              break;
          case '-':
              stack.push(-num);
              break;

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

      
- If `prevOpr` is '`*`' or '`/`', execute the operation immediately, pop the last number from the stack, apply the operation, and push the result back to the stack:
  ```java

            case '*':
                stack.push(stack.pop() * num);
                break;
            case '/':
                stack.push(stack.pop() / num);
                break;
	```

- At last, we have a stack containing a couple of numbers and all of them have the same operator '+'. Finally, sum up all numbers in the stack and return the result:: `while(!stack.isEmpty())res += stack.pop();`

Initialise prevOpr to ‘+’ for the first number:

1

         char prevOpr = '+';

Add an extra ‘+’ to the end of the string to ensure the last number is processed. (as when the last number is added, the prevOpr still needs to execute on it):

1

        s = s + "+"; // kind of hacky but needed

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

public int calculate(String s) {
    if(s==null || s.length()==0) return 0;
    
    Stack<Integer> stack = new Stack<Integer>();
    int num = 0;
    char prevOpr = '+';
    s = s + "+";
    for(int i=0;i<s.length();i++){
	    char ch = s.charAt(i);
	    if (ch == ' ') {
		    continue;
		}
	    else if(Character.isDigit(ch)) {
		    num = ch - '0';
		    while(i+1 < s.length() && Character.isDigit(s.charAt(i+1))) {
				num = num * 10 + s.charAt(i+1) - '0';
				i++;
		    }
		    
	    }else {
		    // as string is valid, we are here that means operator
			switch(prevOpr) {
				case '+':
					stack.push(num);
					break;
				case '-':
					stack.push(-num);
					break;
				case '*':
					stack.push(stack.pop() * num);
					break;
				case '/':
					stack.push(stack.pop() / num);
					break;
				default:
					return -1;
			}
			num = 0;
			prevOpr = ch;
	    }
    }

    int ans = 0;
    for(int stackNum:stack){
        ans += stackNum;
    }
    return ans;
}

Method 2 - Without Using Stack 🏆

A further insight is that we can always sum all stack numbers except the latest one without affecting the result. Thus, we only need two variables instead of a stack:

  • prevNum for the sum of all numbers except the latest one (to be added to the final result after the loop).
  • num for the latest number being processed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

public int calculate(String s) {
    if(s==null || s.length()==0) return 0;
    int num = 0, prevNum = 0, ans = 0;
    char prevOpr = '+';
    s = s + "+";
    for(int i=0;i<s.length();i++){
	    char ch = s.charAt(i);
	    if (ch == ' ') continue;
	    else if(Character.isDigit(ch)) {
		    num = ch - '0';
		    while(i+1 < s.length() && Character.isDigit(s.charAt(i+1))) {
				num = num * 10 + s.charAt(i+1) - '0';
				i++;
		    }
	    } else {
		    // as string is valid, we are here that means operator
			switch(prevOpr) {
				case '+':
					ans += prevNum;
					prevNum = num;
					break;
				case '-':
					ans += prevNum;
					prevNum = -num;
					break;
				case '*':
					prevNum *= num;
					break;
				case '/':
					prevNum /= num;
					break;
				default:
					return -1;
			}
			num = 0;
			prevOpr = ch;
	    }
    }

    
	ans += prevNum;
    return ans;
}

Method 3 - Without Modifying Input String, i.e. without s+"+"

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

    public int calculate2(String s) {
        int result = 0;
        int tempResult = 0;
        int currentNum = 0;
        char currentOp = '+';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = ch - '0';
			    while(i+1 < s.length() && Character.isDigit(s.charAt(i+1))) {
					num = num * 10 + s.charAt(i+1) - '0';
					i++;
			    }
            }
            if (i == s.length() - 1 || !Character.isDigit(c) && c != ' ') {
                switch (currentOp) {
                    case '+':
                        result += tempResult;
                        tempResult = currentNum;
                        break;
                    case '-':
                        result += tempResult;
                        tempResult = -currentNum;
                        break;
                    case '*':
                        tempResult *= currentNum;
                        break;
                    case '/':
                        tempResult /= currentNum;
                        break;
                }
                currentOp = c;
                currentNum = 0;
            }
        }
        result += tempResult;
        return result;
    }