Basic Calculator

Introduction

The basic calculator has the following four questions:

• 224. Basic Calculator I
• 227. Basic Calculator II
• 772. Basic Calculator III
• 770. Basic Calculator IV

The first one contains +, -, (, ). </p> The second one contains +, -, *, /. </p> The third one contains +, -, *, /, (, ).</p> The fourth one contains +, -, *, (, ) and variable replacement. </p>

General Idea

• The parenthesis can be solved by a stack.
  • push the previous temp result and sign to the stack. For example, 1 + (3 + 4). The temp result 1 and sign 1 should be pushed to the stack.
• The *, / can be solved by l2 and o2

General Solution

public int calculate(String s) {
  int l1 = 0, o1 = 1; // Initialization of level one
  int l2 = 1, o2 = 1; // Initialization of level two

  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);

    if (c is a digit) {

        --> we have an operand of type number, so find its value "num"
        --> then evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);

    } else if (c is a lowercase letter) {

        --> we have an operand of type variable, so find its name "var"
        --> then look up the variable mapping table to find its value "num";
        --> lastly evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);

    } else if (c is an opening parenthesis) {

        --> we have an operand of type subexpression, so find its string representation
        --> then recursively call the "calculate" function to find its value "num";
        --> lastly evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);

    } else if (c is a level two operator) {

        --> o2 needs to be updated: o2 = (c == '*' ? 1 : -1);

    } else if (c is a level one operator) {

        --> demotion happens here: l1 = l1 + o1 * l2;
        --> o1 needs to be updated: o1 = (c == '+' ? 1 : -1);
        --> l2, o2 need to be reset: l2 = 1, o2 = 1;

    }

    return (l1 + o1 * l2); // end of expression reached, so demotion happens again
}

Solution

• 224. Basic Calculator I
• 227. Basic Calculator II
• 1. Basic Calculator III
  2. Recursion Solutoin
  3. Stack Solution
• 1. Basic Calculator IV
  2. Recursion Solution

Reference

https://leetcode.com/problems/basic-calculator-iii/discuss/113592/Development-of-a-generic-solution-for-the-series-of-the-calculator-problems