Question

Formatted question description: https://leetcode.ca/all/224.html

 224	Basic Calculator

 Implement a basic calculator to evaluate a simple expression string.

 The expression string may contain
    open ( and closing parentheses ),
    the plus +
    or minus sign -,
    non-negative integers and
    empty spaces .

 Example 1:

 Input: "1 + 1"
 Output: 2

 Example 2:

 Input: " 2-1 + 2 "
 Output: 3

 Example 3:

 Input: "(1+(4+5+2)-3)+(6+8)"
 Output: 23

 Note:
     You may assume that the given expression is always valid.
     Do not use the eval built-in library function.

Algorithm

The title restricts the expressions with only plus and minus signs, numbers, parentheses and spaces, and there is no multiplication and division, so there is no priority of calculation.

A stack is needed to assist the calculation, and a variable sign is used to represent the current symbol.

We traverse the given string s,

  • If you encounter a number, because it may be a multi-digit number, we need to use a while loop to read all the subsequent numbers in, and then use sign*num to update the result res;
  • If a plus sign is encountered, sign is assigned to 1, and if a minus sign is encountered, it is assigned to -1;
  • If a left parenthesis is encountered, push the current result res and sign onto the stack, reset res to 0 and reset to 1;
  • If the closing parenthesis is encountered, the result res is multiplied by the symbol on the top of the stack, the top element of the stack is popped, and the result is res plus the number on the top of the stack, and the top element of the stack is popped.

Code

Java

import java.util.Stack;

public class Basic_Calculator {

    class Solution {
        public int calculate(String s) {
            int res = 0;
            int num = 0;
            int sign = 1;
            int n = s.length();

            Stack<Integer> sk = new Stack<>();

            for (int i = 0; i < n; ++i) {
                char c = s.charAt(i);
                if (c >= '0') {
                    num = 10 * num + (c - '0');
                } else if (c == '+' || c == '-') {
                    res += sign * num; // possible overflow
                    num = 0;
                    sign = (c == '+') ? 1 : -1;
                } else if (c == '(') {
                    sk.push(res); // not c-'0'
                    sk.push(sign);
                    res = 0;
                    sign = 1;
                } else if (c == ')') {
                    res += sign * num;
                    num = 0;
                    res *= sk.peek(); sk.pop(); // sign @note: can be replaced by just `-1*val`
                    res += sk.peek(); sk.pop(); // then previous result
                }
            }
            res += sign * num; // @note: final check, if no ')' to trigger stack pop stuff
            return res;
        }

    }
}

All Problems

All Solutions