224. Basic Calculator
1. Description
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 .
2. Example
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
3. Note
- You may assume that the given expression is always valid.
- Do not use the eval built-in library function.
4. Solutions
My Accepted Solution
n = i_expression.size(), b = number of brackets
Time complexity: O(n)
Space complexity: O(b)
// it is hard to handle brackets, but it is easy to handle + - operations
// so we could use recursive to hanle brackets, when we face a bracket, we use recursive function to remove it
// after this, wo could simplify the expression and make them into simple + - operations
// I use recursive function to do this, and we could also use stack as the same way, I don't want to write it again
class Solution
{
private:
int calculate(const string &i_expression, int &m_index)
{
int result = 0;
int sign = 1; // sign means whether a number is positive or negative, so we can convert '-' to '+'
for( ; m_index < i_expression.size(); m_index++)
{
if(i_expression[m_index] == ' ') continue;
else if(i_expression[m_index] == '+') sign = 1;
else if(i_expression[m_index] == '-') sign = -1;
else if(i_expression[m_index] == '(')
{
m_index++;
result += sign * calculate(i_expression, m_index);
}
else if(i_expression[m_index] == ')')
{
return result;
}
else
{
int index;
for(index = m_index; index < i_expression.size() && ('0' <= i_expression[index] && i_expression[index] <= '9'); index++) ;
int number = stoi(string(i_expression.begin() + m_index, i_expression.begin() + index));
result += sign * number;
m_index = index - 1;
}
}
return result;
}
public:
// int calculate(string s)
int calculate(const string &i_expression)
{
int index = 0;
return calculate(i_expression, index);
}
};