There are several Leetcode problems themed around basic calculator. These problems involve evaluating mathematical expressions represented as strings:

Given a valid math expression as a string, return its corresponding value.

Here are the main problems in this series:

• LC 224. Basic Calculator

  • Supports: +, -, (, )

• LC 227. Basic Calculator II

  • Supports: +, -, *, /

• LC 772. Basic Calculator III

  • Supports: +, -, *, /, (, )

A generic solution template with O(n) time and space complexity for this series is introduced in this discussion post. We reorganize and present the approach in a more intuitive and structured way.

Content

• Variable definition

• Actions

• Template code (based on LC 772. Basic Calculator III)

  • Adaptation for LC 227. Basic Calculator II

  • Adaptation for LC 224. Basic Calculator

Variable definition

• l1: Left operand for addition/subtraction
• o1: Operator for addition/subtraction (1 for +, -1 for -)
• l2: Left operand for multiplication/division
• o2: Operator for multiplication/division (1 for *, -1 for /)

We categorize operations as follows:

• Level-1 operations (lower precedence): +, -
  → Represented by o1 (+ → 1, - → -1)

• Level-2 operations (higher precedence): *, /
  → Represented by o2 (* → 1, / → -1)

Default initialization:

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

This setup allows any number num to be represented as:

num = l1 + o1 * (l2 * num)

with initial values l1 = 0, o1 = 1, l2 = 1

Actions

Case 1. We just parsed a number num

Because * and / (i.e. o2) are of higher precedence than + and -, we evaluate the level-2 operation immediately upon parsing a number.

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

By doing this, we ensure that multiplication and division are resolved before being combined with addition or subtraction at the higher level. As the expression can always be viewed as:

l1 + o1 * (l2 [* or /] num)

Case 2. We just parsed an opening bracket (

An opening bracket signals the start of a new sub-expression. To correctly evaluate it in the context of the outer expression, we must:

1. Save the current state
   Push the current values of l1, o1, l2, and o2 onto a stack. This allows us to return to the outer expression once the sub-expression is evaluated.

2. Reset all variables
   Initialize for evaluating the expression inside the brackets

Example:
For the expression 2 + 3 * (4 - 1), when we encounter the (, we:

• Pause the outer computation of 2 + 3 * by saving the current state (l1 = 2, o1 = 1, l2 = 3, o2 = 1) onto the stack.
• Reset the variables to start fresh and evaluate the sub-expression 4 - 1.

Once the sub-expression is fully evaluated (resulting in 3), it will be merged back into the outer expression as: 2 + 3 * 3 = 11

Case 3. We just parsed a closing bracket )

We want to

1. compute the result of the expression inside the brackets

   we do

   int num = l1 + o1 * l2;
   

   where

   • l1 holds the sum of all the prior +/- chunks

   • l2 is the current multiplication/division results

   • o1 is the current +/- operation

2. restore the outer state

   • we pop the saved values from the stack

3. merge the inner result with the outer part

   • we do

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

   where

   • num is the inner result we just computed

   • l2 and o2 are outer expressions

   e.g.

   • 3 * (2 + 4) → l2 = 3, o2 = 1, num = 6 → now: l2 = 3 * 6 = 18

   • 12 / (2 + 2) → l2 = 12, o2 = -1, num = 4 → now: l2 = 12 / 4 = 3

Case 4. We just parsed a level-2 operator (* or /)

Simply update o2 to prepare for next operation

o2 = (c == '*') ? 1: -1;

Case 5. We just parsed a level-1 operator (+ or -)

We want to

1. Compute the result of the current term

    l1 = l1 + o1 * l2;
   

   where

   • l2 holds the result of any prior multiplication/division

   • o1 is the current + or - operator

2. Store the newly parsed operator

   This operator will be used when the next complete term is merged with l1

3. Reset level-2 states

   We prepare for parsing a new term by resetting the level-2 variables to:

   • Start fresh with a new term: l2 = 1

   • Prepare for potential multiplication or division: o2 = 1

Code

Template code

Based on LC 772 Basic Calculator III - includes + - * / ( )

int calculate(string s) {
      // Level 1: For + or -
      int l1 = 0, o1 = 1;  
      // Level 2: For * or / 
      int l2 = 1, o2 = 1; 

      stack<int> stk;

      for (int i = 0; i < s.length(); ++i) {
          char c = s[i];
      
          if (isdigit(c)) {
              int num = c - '0';
              while (i + 1 < s.length() && isdigit(s[i + 1])) {
                  num = num * 10 + (s[++i] - '0');
              }
              // Apply current multiplication/division operation
              l2 = (o2 == 1 ? l2 * num : l2 / num);

          } else if (c == '(') {
              // Save current state
              stk.push(l1); stk.push(o1);
              stk.push(l2); stk.push(o2);

              // Reset for the new sub-expression (inside the upcoming brackets)
              l1 = 0; o1 = 1;
              l2 = 1; o2 = 1;

          } else if (c == ')') {
              // Compute the result of the expression inside the brackets
              int num = l1 + o1 * l2;

              // Restore the outer state
              o2 = stk.top(); stk.pop();
              l2 = stk.top(); stk.pop();
              o1 = stk.top(); stk.pop();
              l1 = stk.top(); stk.pop();

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

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

          } else if (c == '+' || c == '-') {
              // Apply current term (l2) to result
              l1 = l1 + o1 * l2;
              // Update sign for next term
              o1 = (c == '+' ? 1 : -1); 
              // Reset level 2 computation
              l2 = 1; o2 = 1;
          }
      }

      // Add the last processed value
      return l1 + o1 * l2;
  }

LC 227 Basic Calculator II - includes + - * /

For LC 227. Basic Calculator II, simply delete the code block of dealing with brackets from the template:

else if (c == '(') { ... } 
else if (c == ')') { ... }  

LC 224 Basic Calculator - includes + - ( )

Based on the template:

1. Remove the lines associated with l2, o2

2. Remove the if statement dealing with iterating level-2 operators

    else if (c == '*' || c == '/') { ... }
   

3. Because there are only level-1 operators, the temporary sum is always l1 = l1 + o1 * num;

This is the case for both isdigit(c) and c == ')'

The code becomes

 int calculate(string s) {
    
    int l1 = 0, o1 = 1;  

    stack<int> stk;

    for (int i = 0; i < s.length(); ++i) {
        char c = s[i];
    
        if (isdigit(c)) {
            int num = c - '0';
            while (i + 1 < s.length() && isdigit(s[i + 1])) {
                num = num * 10 + (s[++i] - '0');
            }
            l1 = l1 + o1 * num;

        } else if (c == '(') {
            stk.push(l1); stk.push(o1);
            l1 = 0; o1 = 1;

        } else if (c == ')') {
            int num = l1;

            o1 = stk.top(); stk.pop();
            l1 = stk.top(); stk.pop();

            l1 = l1 + o1 * num;

        } else if (c == '+' || c == '-') {
            o1 = (c == '+' ? 1 : -1); 
        }
    }

    return l1 ;
}