224. Basic Calculator

Hello, reader 👋🏽 ! Welcome to day 50 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 224. Basic Calculator.

🤔 Problem Statement

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
E.g.:
- s = "1 + 1" => 2
- s = "1 + 12" => 13

💬 Thought Process - Stack

This problem is very similar to Evaluate reverse polish notation question.
But here the input is a string instead of a string array.
So it might be difficult to figure out when a number in the input string begins and when it ends.
Because if you notice the input there's no guarantee that the operands, operators and parenthesis are separated by space.
To tackle this, whenever we encounter a first digit we will keep building the number until we come across a non-digit character.
Another thing is that in this problem, we are only dealing with + and -. To figure out if we have to add/ subtract numbers, we'll use an integer variable sign that would be either 1 (indicating that the previous and next numbers need to be added) or -1 indicating the next number and previous number needs to be subtracted.
We'll also hold an answer/ result integer variable to which we would keep adding the intermediate calculations.
To build numbers, we'll use an integer number variable which would initially be 0. To build the number we will multiply the number variable by 10 and then add the current digit.
- For e.g.: if the number in the string is 12, we'll have number = 0 initially.
  - When digit = 1, we will do the following: number = (number * 10) + digit, which results in 1.
  - When digit = 2, we will do the following: number = (number * 10) + digit, which results in 10 + 2 = 12.
Then we multiply this number by the sign and add to the final result
- This is to accommodate the previous operand we encountered. If it is - it means we subtract this number from the result, else we add it.
Then once again we reset the number by 0 as well as sign by 1.
This is repeated until the end of the string.
But if you notice, we also have parentheses which we haven't dealt with yet. This is where the stack comes in.
Since parentheses can be nested, we will use the stack to push the previously calculated values.
When we encounter an opening (, we will push the current result so far and the sign onto the stack. We also reset the result to 0 and sign to 1.
- This is because whatever intermediate result we calculate within parentheses and nested parentheses, we will have to finally add (or subtract) those with the result pushed.
After this, we keep continuing the normal process of building number, multiplying the number by sign and adding to final result.
Once we encounter a matching ), we will pop out the sign and the previous result from the stack, and multiply the current result calculated within the parenthesis with the sign and add to the result.

👩🏽‍💻 Solution - Stack

Below is the code for the above discussed approach.

class Solution {
  public int calculate(String s) {
      Stack<Integer> stack = new Stack();
      int result = 0;
      int number = 0;
      int sign = 1;
      int n = s.length();

      for(int i = 0; i < n; i++) {
          char curr = s.charAt(i);

          if(curr == ' ') continue;
          if(curr >= '0' && curr <= '9') {
              // The number is not guaranteed to be single digit
              int j = i+1;
              number = (number * 10) + (curr - '0');
              while(j < n) {
                  char next = s.charAt(j);
                  if(next >= '0' && next <= '9') {
                      number = (number * 10) + (next - '0');

                  }
                  else {
                      break;
                  }
                  j++;
              }
              i = j-1;
              result += (sign * number);

              sign = +1;
              number = 0;
          }
          else if(curr == '+') {
              sign = 1;
          }
          else if(curr == '-') {
              // This means that the next number will be subtracted from the result
              sign = -1;
          }
          else if(curr == '(') {
              stack.push(result);
              stack.push(sign);

              // reset the result and sign
              result = 0;
              sign = 1;
          }
          else {
              int stackTopSign = stack.pop();
              int stackTopResult = stack.pop();

              // pop the previos result and add/ subtract the intermediate values from result
              result = stackTopResult + (stackTopSign * result);
          }
      }

      return result;
  }
}

Time Complexity: O(n)
  - n = length of string
Space Complexity: O(n)
  - n = length of string

You can find the link to the GitHub repo for this question here: 224. Basic Calculator.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian