Solution: Basic Calculator

Let's solve the Basic Calculator problem using the Stacks pattern.

We'll cover the following

Statement

Given a string containing an arithmetic expression, implement a basic calculator that evaluates the expression string. The expression string can contain integer numeric values and should be able to handle the “+” and “-” operators, as well as “()” parentheses.

Constraints:

Let s be the expression string. We can assume the following constraints:

  • 1≤1 \leq s.length ≤3×103\leq 3 \times 10^{3}
  • s consists of digits, “+”, “-”, “(”, and “)”.
  • s represents a valid expression.
  • “+” is not used as a unary operation ( +1+1 and +(2+3)+(2 + 3) are invalid).
  • “-” could be used as a unary operation (−1-1 and −(2+3)-(2 + 3) are valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.

Pattern: Stacks

While calculating the arithmetic expression, we evaluate the individual subexpressions. We need to store the results of these intermediate calculations in place of those subexpressions. Then we’ll need to get back the most recent stored result.

A feature of this problem is that subexpressions can be nested, one within another. This arrangement can be easily mimicked during the evaluation of these subexpressions by pushing them to the stack and then popping them as we return from nesting. So these operations can be performed using the basic methods of the stack—that is, push and pop.

Solution

The slides below illustrate how we’d like the algorithm to run:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

Let’s start with the simplest step—we’ll iterate the whole expression character by character. If a digit is found, we need to form the operand by multiplying the previously formed operand by 1010 and adding the current digit to it. If we encounter any other operator, we’ll simply reset the variable.

The highlighted lines implement this logic:

import java.util.*;
class BasicCalculator {
    public static boolean dbg;
    public static String printStringWithMarkers(String strn, int pValue) {
        String out = "";
        for (int i = 0; i < pValue; i++) {
            out += String.valueOf(strn.charAt(i));
        }
        out += "«";
        out += String.valueOf(strn.charAt(pValue)) + "»";
        for (int i = pValue + 1; i < strn.length(); i++) {
            out += String.valueOf(strn.charAt(i));
        }
        return out;
    }
    public static String calculator(String expression) {
        int number = 0;
        int sign = 1;
        int output = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (dbg) {
                System.out.println("\t\t" + printStringWithMarkers(expression, i));
                System.out.println("\t\tCurrent character: '" + c + "'");
            }
            // To store the consecutive digits that is 52 => 5 x 10 + 2 = 52
            if (Character.isDigit(c)) {
                int temp = number;
                number = number * 10 + Character.getNumericValue(c); // for consecutive digits 98 => 9x10 + 8 = 98
                if (dbg) System.out.println("\t\tDetected digit, updating operand: " + temp + " * 10 + " + c + " = " + number);
            }
            // Evaluate the left expression and store the new sign value
            if (c == '-' || c == '+') {
                if (dbg) {
                    System.out.println("\t\tOperator encountered");
                    System.out.println("\t\t\tResetting Operand: " + number + " ⟶ 0\n");
                }
                number = 0;
            }
            if (dbg) System.out.println();
        }
        return "None";
    }
    public static void main(String args[]) {
        String[] input = {
                "4 + (52 - 12) + 99",
                "(31 + 7) - (5 - 2)",
                "(12 - 9 + 4) + ( 7 - 5)",
                "8 - 5 + (19 - 11) + 6 + (10 + 3)",
                "56 - 44 - (27 - 17 - 1) + 7"
        };
        for (int i = 0; i < input.length; i++) {
            // Set to False to suppress line-by-line trace
            dbg = true;
            System.out.println((i + 1) + "." + "\tGiven Expression: " + input[i]);
            if (dbg) System.out.println("\n\t\tProcessing...");
            System.out.println("\tThe result is:  " + calculator(input[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Basic Calculator

When we encounter the “+” or “-” operators, we first evaluate the expression to the left and save the sign value for the next evaluation (lines 49–57):

import java.util.*;
class BasicCalculator {
    public static boolean dbg;
    public static String printStringWithMarkers(String strn, int pValue) {
        String out = "";
        for (int i = 0; i < pValue; i++) {
            out += String.valueOf(strn.charAt(i));
        }
        out += "«";
        out += String.valueOf(strn.charAt(pValue)) + "»";
        for (int i = pValue + 1; i < strn.length(); i++) {
            out += String.valueOf(strn.charAt(i));
        }
        return out;
    }
    public static int calculator(String expression) {
        // We'll use sign_value variable to represent the
        // positive or negative operator
        int signValue = 1;
        int number = 0;
        int result = 0;
        int temp = 0;
        for (int i = 0; i < expression.length(); i++) {
            // To store the consecutive digits that is 52 => 5 x 10 + 2 = 52
            char c = expression.charAt(i);
            if (dbg) {
                System.out.println("\t\t" + printStringWithMarkers(expression, i));
                System.out.println("\t\tCurrent character: '" + c + "'");
            }
            if (Character.isDigit(c)) {
                temp = number;
                number = number * 10 + Character.getNumericValue(c);
                if (dbg) System.out.println("\t\tDetected digit, updating operand: " + temp + " * 10 + " + c + " = " + number);
            }
            // Evaluate the left expression and store the new sign value
            else if (c == '+' || c == '-') {
                temp = result;
                if (dbg) {
                    System.out.println("\t\tOperator encountered");
                    System.out.println("\t\t\tUpdating result: " + result + " + " + number + " * " + signValue + " ⟶ " + (result + number * signValue));
                    if (c == '-') System.out.println("\t\t\tUpdating sign value to: -1");
                    else System.out.println("\t\t\tUpdating sign value to: 1");
                    System.out.println("\t\t\tResetting Operand: " + number + " ⟶ 0");
                }
                result += number * signValue;
                if (c == '-') signValue = -1;
                else signValue = 1;
                number = 0;
            }
            if (dbg) System.out.println();
            // Push the result calculated till now and store the sign value
        }
        return result + number;
    }
    public static void main(String args[]) {
        String[] input = {
            "4 + (52 - 12) + 99",
            "(31 + 7) - (5 - 2)",
            "(12 - 9 + 4) + ( 7 - 5)",
            "8 - 5 + (19 - 11) + 6 + (10 + 3)",
            "56 - 44 - (27 - 17 - 1) + 7"
        };
        int num = 1;
        for (int i = 0; i < input.length; i++) {
            // Set to False to suppress line-by-line trace
            dbg = true;
            System.out.println((i + 1) + "." + "\tGiven Expression: " + input[i]);
            if (dbg) System.out.println("\n\t\tProcessing...");
            System.out.println("\tThe result is:  " + calculator(input[i]));
            num += 1;
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Basic Calculator

If “(” is found, we push the result calculated so far and the sign value onto the stack (lines 63–72):

import java.util.*;
class BasicCalculator {
    public static boolean dbg;
    public static String printStringWithMarkers(String strn, int pValue) {
        String out = "";
        for (int i = 0; i < pValue; i++) {
            out += String.valueOf(strn.charAt(i));
        }
        out += "«";
        out += String.valueOf(strn.charAt(pValue)) + "»";
        for (int i = pValue + 1; i < strn.length(); i++) {
            out += String.valueOf(strn.charAt(i));
        }
        return out;
    }
    public static String calculator(String expression) {
        // We'll use sign_value variable to represent the
        // positive or negative operator
        int signValue = 1;
        int number = 0;
        int result = 0;
        int temp = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            // To store the consecutive digits that is 52 => 5 x 10 + 2 = 52
            char c = expression.charAt(i);
            if (dbg) {
                System.out.println("\t\t" + printStringWithMarkers(expression, i));
                System.out.println("\t\tCurrent character: '" + c + "'");
            }
            if (Character.isDigit(c)) {
                temp = number;
                number = number * 10 + Character.getNumericValue(c);
                if (dbg)
                    System.out.println("\t\tDetected digit, updating operand: " + temp + " * 10 + " + c + " = " + number);
            }
            // Evaluate the left expression and store the new sign value
            else if (c == '+' || c == '-') {
                if (dbg) {
                    System.out.println("\t\tOperator encountered");
                    System.out.println("\t\t\tUpdating result: " + result + " + " + number + " * " + signValue + " ⟶ " + (result + number * signValue));
                    if (c == '-')
                        System.out.println("\t\t\tUpdating sign value to: -1");
                    else
                        System.out.println("\t\t\tUpdating sign value to: 1");
                    System.out.println("\t\t\tResetting Operand: " + number + " ⟶ 0");
                }
                temp = result;
                result += number * signValue;
                if (c == '-')
                    signValue = -1;
                else
                    signValue = 1;
                number = 0;
            }
            // Push the result calculated till now and store the sign value
            else if (c == '(') {
                if (dbg) {
                    System.out.print("\t\tDetected '(', push intermediate result, " + result + ", and sign value, " + signValue + ", to the operations_stack:\n\t\t\t" + stack + " ⟶ ");
                }
                stack.push(result);
                stack.push(signValue);
                if (dbg)
                    System.out.println(stack);
                result = 0;
                signValue = 1;
            }
            if (dbg)
                System.out.println();
        }
        return "None";
    }
    public static void main(String args[]) {
        String[] input = {
            "4 + (52 - 12) + 99",
            "(31 + 7) - (5 - 2)",
            "(12 - 9 + 4) + ( 7 - 5)",
            "8 - 5 + (19 - 11) + 6 + (10 + 3)",
            "56 - 44 - (27 - 17 - 1) + 7"
        };
        for (int i = 0; i < input.length; i++) {
            // Set to False to suppress line-by-line trace
            dbg = true;
            System.out.println((i + 1) + "." + "\tGiven Expression: " + input[i]);
            if (dbg)
                System.out.println("\n\t\tProcessing...");
            System.out.println("\tThe result is:  " + calculator(input[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Basic Calculator

If “)” is found, we’ll perform two tasks:

  • We’ll calculate the expression to the left. The result of this would be the result of the expression within the set of parenthesis that just ended.

  • Pop the sign value from the top of the stack (that we stored before starting the open parenthesis) and multiply it with the computed result within the parenthesis. Then we’ll pop the previously stored result from the stack and add it with the result of parenthesis.

The highlighted lines implement this logic:

import java.util.Stack;
class BasicCalculator {
    public static boolean dbg;
    public static String printStringWithMarkers(String strn, int pValue) {
        String out = "";
        for (int i = 0; i < pValue; i++) {
            out += String.valueOf(strn.charAt(i));
        }
        out += "«";
        out += String.valueOf(strn.charAt(pValue)) + "»";
        for (int i = pValue + 1; i < strn.length(); i++) {
            out += String.valueOf(strn.charAt(i));
        }
        return out;
    }
    public static int calculator(String expression) {
        // We'll use signValue variable to represent the positive or negative operator
        int signValue = 1;
        int number = 0;
        int result = 0;
        int temp = 0;
        int secondValue = 0;
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < expression.length(); i++) {
            // To store the consecutive digits that is 52 => 5 x 10 + 2 = 52
            char c = expression.charAt(i);
            if (dbg) {
                System.out.println("\t\t" + printStringWithMarkers(expression, i));
                System.out.println("\t\tCurrent character: '" + c + "'");
            }
            
            if (Character.isDigit(c)) {
                temp = number;
                number = number * 10 + Character.getNumericValue(c);
                if (dbg) 
                    System.out.println("\t\tDetected digit, updating operand: " + temp + " * 10 + " + c + " = " + number);
            }
            // Evaluate the left expression and store the new sign value
            else if (c == '+' || c == '-') {
                if (dbg) {
                    System.out.println("\t\tOperator encountered");
                    System.out.println("\t\t\tUpdating result: " + result + " + " + number + " * " + signValue + " ⟶ " + (result + number * signValue));
                    if (c == '-')
                        System.out.println("\t\t\tUpdating sign value to: -1");
                    else
                        System.out.println("\t\t\tUpdating sign value to: 1");
                    System.out.println("\t\t\tResetting Operand: " + number + " ⟶ 0");
                }
                temp = result;
                result += number * signValue;
                if (c == '-')
                    signValue = -1;
                else
                    signValue = 1;
                number = 0;
            }
            // Push the result calculated till now and store the sign value
            else if (c == '(') {
                if (dbg) {
                    System.out.print("\t\tDetected '(', push intermediate result, " + result + ", and sign value, " + signValue + ", to the \n\t\toperations_stack:" + stack + " ⟶ ");
                }
                stack.push(result);
                stack.push(signValue);
                if (dbg)
                    System.out.println(stack);
                result = 0;
                signValue = 1;
            }
            // Convert current number to positive or negative if we need
            // to perform an addition or a subtraction respectively
            // and add it to the previously calculated result
            else if (c == ')') {
                result += signValue * number;
                if (dbg) {
                    System.out.println("\t\tCurrent result: " + result);
                    System.out.println("\t\tDetected ')', we'll pop the sign value from the operationsStack");
                    System.out.print("\t\t\t" + stack);
                }
                int popSignValue = stack.pop();
                if (dbg) {
                    System.out.println(" ⟶ " + stack);
                    System.out.println("\t\tSign value: " + popSignValue);
                }
                temp = result;
                result *= popSignValue;
                if (dbg) {
                    System.out.println("\t\tUpdating result: " + temp + " * " + popSignValue + " = " + result);
                    System.out.println("\t\tPopping from the operationsStack to get the second value");
                    System.out.print("\t\t\t" + stack);
                }
                secondValue = stack.pop();
                if (dbg) {
                    System.out.println(" ⟶ " + stack);
                    System.out.println("\t\tSecond value: " + secondValue);
                    System.out.println("\t\tUpdating result: " + result + " + " + secondValue + " = " + (result + secondValue));
                }
                result += secondValue;
                if (dbg) {
                    System.out.println("\t\tFinal result value is " + result + " and operationsStack is " + stack);
                }
                number = 0;
            }
            
            if (dbg)
                System.out.println();
        }
        
        return result + number * signValue;
    }
    public static void main(String args[]) {
        String[] input = {
            "4 + (52 - 12) + 99",
            "(31 + 7) - (5 - 2)",
            "(12 - 9 + 4) + ( 7 - 5)",
            "8 - 5 + (19 - 11) + 6 + (10 + 3)",
            "56 - 44 - (27 - 17 - 1) + 7"
        };
        
        for (int i = 0; i < input.length; i++) {
            // Set to False to suppress line-by-line trace
            dbg = true;
            System.out.println((i + 1) + "." + "\tGiven Expression: " + input[i]);
            if (dbg)
                System.out.println("\n\t\tProcessing...");
            System.out.println("\tThe result is:  " + calculator(input[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Basic Calculator

Just the code

Here’s the complete solution to this problem:

import java.util.*;
class BasicCalculator {
    public static String printStringWithMarkers(String strn, int pValue) {
        String out = "";
        for (int i = 0; i < pValue; i++) {
            out += String.valueOf(strn.charAt(i));
        }
        out += "«";
        out += String.valueOf(strn.charAt(pValue)) + "»";
        for (int i = pValue + 1; i < strn.length(); i++) {
            out += String.valueOf(strn.charAt(i));
        }
        return out;
    }
    public static int calculator(String expression) {
        int signValue = 1;
        int number = 0;
        int result = 0;
        int secondValue = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (Character.isDigit(c)) {
                number = number * 10 + Character.getNumericValue(c);
            } else if (c == '+' || c == '-') {
                result += number * signValue;
                if (c == '-')
                    signValue = -1;
                else
                    signValue = 1;
                number = 0;
            } else if (c == '(') {
                stack.push(result);
                stack.push(signValue);
                result = 0;
                signValue = 1;
            } else if (c == ')') {
                result += signValue * number;
                int popSignValue = stack.pop();
                result *= popSignValue;
                secondValue = stack.pop();
                result += secondValue;
                number = 0;
            }
        }
        return result + number * signValue;
    }
    public static void main(String args[]) {
        String[] input = {
            "4 + (52 - 12) + 99",
            "(31 + 7) - (5 - 2)",
            "(12 - 9 + 4) + (7 - 5)",
            "8 - 5 + (19 - 11) + 6 + (10 + 3)",
            "56 - 44 - (27 - 17 - 1) + 7"
        };
        for (int i = 0; i < input.length; i++) {
            System.out.println((i + 1) + "." + "\tGiven Expression: " + input[i]);
            System.out.println("\tThe result is:  " + calculator(input[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Basic Calculator

Solution summary

To recap, the solution to this problem can be divided into the following four parts:

  • Store the consecutive digits.
  • On detecting “+” or “-”, evaluate the left expression and store the new sign value.
  • On detecting “(”, push the result calculated until now and store the sign value
  • On detecting “)”, convert the current number to be positive or negative if we need to perform an addition or a subtraction respectively, and add it to the previously calculated result.

Time complexity

Since we are only traversing the string once, the time complexity of the algorithm above is O(n)O(n), where nn is the length of the string.

Space complexity

The space complexity is O(n)O(n) in the worst case, where most of the expression is a series of nested sub-expressions.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.