Problem

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().%% %%

Examples

Example 1:

Input:
s = "1 + 1"
Output:
 2

Example 2:

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

Example 3:

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

Constraints

  • 1 <= s.length <= 3 * 105
  • s consists of digits, '+', '-', '(', ')', and ' '.
  • s represents a valid expression.
  • '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
  • '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.

Solution

This problem can be addressed using a stack by continuously pushing elements onto it. When encountering ‘)’, evaluate the expression up to the preceding ‘(’.

Method 1 - Using Stack of Numbers and Sign

Due to constraints, we must handle unary minus, so we use a sign variable. This method is a simple iterative solution that processes characters one by one, assuming valid input with correctly paired and ordered parentheses.

We need to consider only five types of input:

  1. Digit: Form part of the current number.
  2. ’+’: Indicates the end of a number, prompting a sign change.
  3. ’-’: Similar to ‘+’ but signifies a negative number.
  4. ’(’: Push the current result and sign onto the stack, reset result to 0, and compute the new result within the parenthesis.
  5. ’)’: Pop the top two elements from the stack; the first is the sign preceding the parenthesis, and the second is the temporary result. Combine these with the current result.

If there is only one number left unprocessed, ensure it has been added to the final result by checking if the number is not zero.

Code

Java
public static int calculate(String s) {
	int sign = 1, ans = 0;
	Stack<Integer> stack = new Stack<Integer>();
	for (int i = 0; i < s.length(); i++) {
		char ch = s.charAt(i);
		if (Character.isDigit(ch )) {
			int sum = ch - '0';
			while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
				sum = sum * 10 + s.charAt(i + 1) - '0';
				i++;
			}
			ans += sum * sign;
		} else if (ch  == '+')
			sign = 1;
		else if (ch  == '-')
			sign = -1;
		else if (ch  == '(') {
			stack.push(ans);
			stack.push(sign);
			ans = 0;//as we calculate the new value, 
			        // and prev value is already pushed to stack
			sign = 1;
		} else if (ch  == ')') {
			// first pop for sign, and next for operand
			ans = ans * stack.pop() + stack.pop();
		}

	}
	return ans;
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the input string (s).
  • 🧺 Space complexity: O(n) for using the stack.