How can I evaluate an infix string expression which only consists of +
and *
operators. (No parenthesis).
Example 1:
"1+2*3"
7
Example 2:
"1+2*3+4"
11
Here is my code I have so far (which is not giving correct result), I wonder if I can do it with one stack (or none)
int evaluateExpression(string s) {
stack<int> operandStack;
stack<char> operatorStack;
string token = "";
for(char &c : s) {
if(c == '*' || c == '+') {
operandStack.push(stoi(token));
operatorStack.push(c);
token = "";
}
else {
token += c;
}
if(operandStack.size() > 1
&& operandStack.size() == operatorStack.size() + 1
&& operatorStack.top() == '*') {
int a = operandStack.top(); operandStack.pop();
int b = operandStack.top(); operandStack.pop();
operandStack.push(a * b);
}
}
while(operandStack.size() > 1) {
int a = operandStack.top(); operandStack.pop();
int b = operandStack.top(); operandStack.pop();
operandStack.push(a + b);
}
return operandStack.top();
}
Note: do not want to use any non-standard libraries. Ideally with no use of any library.
int evaluateExpression(string s) {
string token = "";
char currOperator = '+';
stack<int> st;
string temp = s + '.';
for(const char &c : temp) {
if(isdigit(c)) {
token += c;
}
else if(c != ' ') {
if(currOperator == '*') {
int stackTop = st.top();
st.pop();
st.push(stackTop * stoi(token));
}
else if(currOperator == '+') {
st.push(stoi(token));
}
token = "";
currOperator = c;
}
}
int result = 0;
while(!st.empty()) {
result += st.top();
st.pop();
}
return result;
}