Posts Basic Calculator
Post
Cancel

Basic Calculator

PROBLEM DESCRIPTION

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().

leetcode

SOLUTION

leetcode editorial

Example:

(7-8+9)

Let’s add to stack from left to right:

1
2
3
4
5
6
7
8
Stack:
)
9
+
8
-
7
(

This will evaluate to:

1
2
3
4
5
6
Stack:
)
17
-
7
(

This will evaluate to:

1
2
3
4
Stack:
)
10
(

This is a WRONG ANSWER!

This happens because unlike addition, subtraction is not commutative or associative. If we use a stack and read the elements of the expression from left to right, we end up evaluating the expression from right-to-left. This means we are expecting (A−B)−C(A-B)-C(A−B)−C to be equal to (C−B)−A(C-B)-A(C−B)−A which is not correct.

To handle this, we can go from right to left instead.

The stack will look like this:

(7-8+9)

1
2
3
4
5
6
7
(
7
-
8
+
9
)

Which evaluates to:

1
2
3
4
5
(
-1
+
9
)

Which evaluates to:

1
2
3
(
8
)
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
class Solution {
    
    public int evaluateCurrentState(Stack<Object> stack){

        //if stack is empty or the top most element is not an integer, then add 0 to make it simpler to calculate
        if(stack.isEmpty() || !(stack.peek() instanceof Integer)){
            stack.push(0);
        }

        //init: start the calculation using top most element (which is why we had added 0 earlier to make this part simpler)
        //if the top was already a digit, that's alright too
        int res = (int) stack.pop();

        //it's possible that there are no brackets and stack can become empty, so check if stack is not empty
        //we need to evaluate till the corresponding closing bracket
        while(!stack.isEmpty() && (char)stack.peek() != ')'){
            
            //next character must be the sign 
            char sign = (char) stack.pop();

            //calculate based on sign
            //the next popped number will be the next digit
            if(sign == '+'){
                res += (int) stack.pop();
            }else{
                res -= (int) stack.pop();
            }

        }

        return res;

    }

    public int calculate(String s) {
        
        //create a stack of Object type because it needs to have both integers and characters for operations/signs 
        Stack<Object> stack = new Stack<>();

        //we will form the operand which needs to be added or subtracted while iterating through the string from right to left
        //example: 1 + 123
        //since we are iterating from right, first we meet 3
        //operand += 3 * (10 power 0)
        //increment the power (p) for the next digit
        //but we don't add the number to the stack yet
        //next digit is 2. 
        //operand += 2 * (10 power 1), because p is now 1
        //similary, operand += 1 * (10 power 2)
        //we have formed the operand 123, but not yet added it to the stack
        //we will add it when we encounter a non-integer
        int operand = 0;
        int p = 0; //power

        //loop from right to left
        for(int i=s.length()-1; i>=0; i--){

            //get current character
            char c = s.charAt(i);

            //if current character is a digit
            if(Character.isDigit(c)){
                
                //add to the operand and increment the power value for the next digit
                operand += (int)Math.pow(10, p) * (int)(c-'0');
                p++;

            //if the next character is not a space
            }else if(c != ' '){
                
                //it's possible that we had formed some operand which is yet to be added
                //this can be checked by checking the value of power p
                //if this is not 0, it means, there must be some operand and we can add it to the stack
                //remember to reset the value of operand and power for subsequent numbers which might come up
                if(p != 0){
                    stack.push(operand);
                    operand = 0;
                    p = 0;
                }

                //if we encounter an opening bracket, we have found a pair and we can calculate the result of this sub-expression
                if(c == '('){
                    
                    //calculate value for the subexpression
                    int res = evaluateCurrentState(stack);

                    //pop the opening bracket (remember, we are going in reverse)
                    stack.pop();

                    //push the current result to the stack
                    //this may be used for subsequent evaluation
                    stack.push(res);

                }else{

                    //otherwise, push to stack
                    stack.push(c);
                }

            }

        }

        //if power is not 0, we have some operand which is yet to be added to the stack
        //example expression: 1234 -> this will form the operand but never get added in the for-loop
        if(p != 0){
            stack.push(operand); 
        }

        //evaluate any left overs in the stack and return the final answer
        return evaluateCurrentState(stack);

    }

}
This post is licensed under CC BY 4.0 by the author.