Problem:

Given a string s which represents an expression, evaluate this expression and return its value.

Assumptions and General Information:

• The integer division should truncate toward zero.
• You may assume that the given expression is always valid. All intermediate results will be in the range of [(-2^31), (2^31) - 1].
• No built-in functions are allowed.
• s represents a valid expression.
• All the integers in the expression are non-negative integers in the range [0, (2^31) - 1].

Examples

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

Input: s = "1 + 2 * 3 - 5 / 4"
Output: 6

Input: s = "2 * 35 - 7"
Output: 63

Constraints

• 1 <= s.length <= 3 * (10 ^ 5).

• s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.

• The answer is guaranteed to fit in a 32-bit integer.

Solution

Brute Force

A naive approach to solve this problem would be to iterate through the string and find the operator with the highest precedence (in the order '/', '*', '+', '-') as per the BODMAS principle and perform the operation on the number preceding and succeeding the operator. We need to remember that we need to look for the number until we hit another operator or the lower or upper bounds of the string. We then calculate the result and save it. We then create another string with this intermediate result and move forward to the next operator.

Since we have 4 operators, we perform this 4 times. By the end of it we should have a string that can be typecasted to a string. We also try to find the numbers (instead of digits) on each side of the operator.The maximum time taken for this operation can also be n. Therefore, the time complexity will be O(n^2) and the space complexity includes creating a string for each of the iterations. Therefore, the space complexity of another O(n).

First Approach

We can use a stack to evaluate these expressions. Think of it as only one operation that needs to be performed on numbers in a stack. This would be a O(n) solution. In order for us to achieve that, we should evaluate all the other operations so that only one low precedence operation is left.
Let us assume addition as that operation.

For example, "1 + 2 * 3 - 5/ 4" can be simplified to "1 + 6 - 1". This can also be written as "1 + 6 + (-1)". If we have 1, 6 and -1 in the stack, we can just return their sum.

In order to implement this, we keep track of a current number and a current operator. When the current operator is '+', we just add the number to the stack. For '-', we add -1 times the number to the stack. For '*' and '/', we take the current top of the stack, perform the operation with the current number and put it back on to the stack. Towards the end, we will have a stack that contains elements that need to be added.

Code

public int calculate(String s) {
    char[] strArray = s.toCharArray();
    int currentNumber = 0;
    char operator = '+';
    Stack<Integer> stack = new Stack<>();
    int currentTop = -1;
    int newTop = -1;

    for (int i = 0; i < strArray.length; i++) {
        char currentChar = strArray[i];
        if (Character.isDigit(currentChar)) {
            currentNumber = currentNumber * 10 + currentChar - '0';
        }

        if ((!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar)) || (i == strArray.length - 1)) {
            switch (operator) {
                case '+':
                    stack.push(currentNumber);
                    break;
                case '-':
                    stack.push(-1 * currentNumber);
                    break;
                case '*':
                    currentTop = stack.pop();
                    newTop = currentTop * currentNumber;
                    stack.push(newTop);
                    break;
                case '/':
                    currentTop = stack.pop();
                    newTop = currentTop / currentNumber;
                    stack.push(newTop);
                    break;
            }

            operator = currentChar;
            currentNumber = 0;
        }
    }

    int sum = 0;
    while (!stack.empty()) {
        sum += stack.pop();
    }

    return sum;
}

Optimized Approach

The above solution with a stack has a time complexity of O(n). However, the space complexity is also O(n) because we need to save elements onto a stack and the size of the stack varies with the input.

This problem can be solved in O(1) or constant space complexity. We will be making some changes to the above algorithm in order to avoid using the stack.

For this, we will use an integer variable called result, which will hold the intermediate result. Therefore, instead of saving elements to the stack, we just add them to result. However, there is an issue with '*' and '/', where we save the partial results to the stack. To avoid that, we will use another variable called lastNumber to hold the partial result.

Using these two variables, we can avoid using the stack therefore reduce the space complexity.

Code

public int calculate(String s) {
    char[] strArray = str.toCharArray();
    int currentNumber = 0;
    char currentOperator = '+';
    int result = 0;
    int lastNumber = 0;

    for(int i = 0; i < strArray.length; i++) {
        char currentChar = strArray[i];

        if(isDigit(currentChar)) {
            currentNumber = currentNumber * 10 + currentChar - '0';
        }

        if(!isDigit(currentChar) && !isWhitespace(currentChar) || i == strArray.length - 1) {
            switch(currentOperator) {
                case '+':
                    result += lastNumber;
                    lastNumber = currentNumber;
                    break;
                case '-':
                    result += lastNumber;
                    lastNumber = -1 * currentNumber;
                    break;
                case '*':
                    lastNumber = lastNumber * currentNumber;
                    break;
                case '/':
                    lastNumber = lastNumber / currentNumber;
                    break;
            }

            if(i == strArray.length - 1) {
                result += lastNumber;
            }

            currentNumber = 0;
            currentOperator = currentChar;
        }
    }
    return result;
}