# [leetcode] Basic Calculator

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 .

You may assume that the given expression is always valid.

Some examples:

```"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
```

Note: Do not use the `eval` built-in library function.

```//(5), () valid?
//Step 1. convert to reverse polish notation
//Step 2. cal the reverse polish notation expression
//Can the operand overflow 32btis?
class Solution {
public:
int calculate(string s) {
vector<string> rpn;
long ans = 0;
stack<char> st;
stack<long> ist;
size_t i = 0;
while(i < s.size()){
char c = s[i];
if(c == ' ' || c == '\t'){
i++;
continue;
}
if(isOperator(c)){
// + - * /
//If stack is empty, push it
//If the priority of c is higher than the element on the top, or element on the top is '('', push it
//While the priority of c is lower or equal to the element on the top, pop stack to ans
if(st.empty()){
st.push(c);
i++;
}
else if(getPriority(c) > getPriority(st.top())){
st.push(c);
i++;
}
else{
rpn.push_back(string(1, st.top()));//BUG HERE, not to_string()
st.pop();
}
}
else if(isLeftParenthese(c)){
st.push(c);
i++;
}
else if(isRightParenthese(c)){
if(isLeftParenthese(st.top())){
st.pop();
i++;
}
else{
rpn.push_back(string(1, st.top()));//BUG HERE
st.pop();
}
}
else{
//operand, may be multiple digits "23"
int j = i;
while(isDigit(s[j]) && j < s.size()){
j++;
}
rpn.push_back(s.substr(i, j - i));
i = j;
}
}
//push the last operator in rpn string
while(st.empty() == false){
rpn.push_back(string(1, st.top()));//BUG HERE
st.pop();
}

//cal reverse polish notation
for(auto it = rpn.begin(); it != rpn.end(); it++){
string s = *it;
if(isDigit(s[0])){
long num = 0;
for(size_t i = 0; i < s.size(); i++){
num = num * 10 + s[i] - '0';
//i++; BUG HERE
}
ist.push(num);
}
else{
//operator
char c = (*it)[0];
long operand1 = ist.top();
ist.pop();
long operand2 = ist.top();
ist.pop();
long ans = 0;
switch(c){
case '+':
ans = operand2 + operand1;
break;
case '-':
ans = operand2 - operand1;
break;
case '*':
ans = operand2 * operand1;
break;
case '/':
ans = operand2 / operand1;
break;
}
ist.push(ans);
}
}
return ist.top();
}
bool isOperator(char c){
if(c == '-' || c == '+' || c == '*' || c == '/')
return true;
else{
return false;
}
}
bool isLeftParenthese(char c){
return c == '(';
}
bool isRightParenthese(char c){
return c == ')';
}
int getPriority(char c){
if(c == '*' || c == '/'){
return 2;
}
else if(c == '+' || c == '-'){
return 1;
}
else {
return 0;//left parenthese
}
}
bool isDigit(char c){
return c <= '9' && c >= '0';
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.