227. Basic Calculator II
1. Description
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
2. Example
Example 1:
Input: s = “3+2*2”
Output: 7
Example 2:
Input: s = " 3/2 "
Output: 1
Example 3:
Input: s = " 3+5 / 2 "
Output: 5
3. Constraints
- 1 <= s.length <= $3 * 10^5$
- s consists of integers and operators ('+', ‘-’, ‘*’, ‘/') separated by some number of spaces.
- s represents a valid expression.
- All the integers in the expression are non-negative integers in the range [0, $2^{31} - 1$].
- The answer is guaranteed to fit in a 32-bit integer.
4. Solutions
My Accepted Solution
n = m_expression.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
private:
bool isDigit(char letter)
{
return '0' <= letter && letter <= '9';
}
bool isSign(char letter)
{
return letter == '+' || letter == '-' || letter == '*' || letter == '/';
}
public:
// int calculate(string s)
int calculate(string &m_expression)
{
vector<int> numbers;
m_expression.push_back('+'); // add a sign to handle the last number, or will end with losing the last number
for(int i = 0, left = -1, right = -1, lastSign = '+'; i < m_expression.size(); i++)
{
// left and right means two borders of a number
char letter = m_expression[i];
if(isDigit(letter))
{
if(left == -1) left = i;
right = i;
}
else if(isSign(letter))
{
int number = stoi(m_expression.substr(left, right - left + 1));
left = right = -1;
if(lastSign == '+')
numbers.push_back(number);
else if(lastSign == '-')
numbers.push_back(-number);
else if(lastSign == '*')
*numbers.rbegin() = numbers.back() * number;
else if(lastSign == '/')
*numbers.rbegin() = numbers.back() / number;
lastSign = letter;
}
}
return accumulate(numbers.begin(), numbers.end(), 0);
}
};