Search code examples
c++algorithmexpressioninfix-notationinfix-operator

Evaluate infix string expression consisting of only addition and multiplication


How can I evaluate an infix string expression which only consists of + and * operators. (No parenthesis).

Example 1:

  • Input: "1+2*3"
  • Output: 7

Example 2:

  • Input: "1+2*3+4"
  • Output: 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.


Solution

  •  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;
        }