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.
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.