CODEWITHSUNDEEP
c++algorithmexpressioninfix-notationinfix-operator
A-Sharabiani
A-Sharabiani

Reputation: 19377

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:

Example 2:

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.

Upvotes: -3

Views: 655

Answers (2)

A-Sharabiani
A-Sharabiani

Reputation: 19377

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

Upvotes: 0

A M
A M

Reputation: 15265

Yes, you do need only one stack. You can use the standard approach with a shift-reduce parser. In your case, and the simple grammar, this may be already a little bit too much. But I will describe it anyway.

The secret is to use a "parse stack". So only one stack. Not an operator and operand stack. There you will use attributed tokens. A token has a type, like ADD, MULT, NUMBER and, an associated attribute. The attribute is usually a union or a struct. It would be empty for ADD and MULT and would contain a value for NUMBER.

The scanner, which has usually the function getNextToken will produce your tokens. In your case, extremely simple, just those 3 tokens.

Then, in a loop, you will do always the following actions.

  • Always push the fresh token onto the parse stack
  • Try to match the top of the stack with a production of the grammar (and look ahead token)
  • Reduce the stack (Remove matched elements), evaluate the expression, and put the result on the parse stack

So, always: Shift, Match, Reduce

In your case you need for the match function one lookahead symbol, so, the next token. You will find exactly such an example here. There you can find a compiler, with one front end (Scanner, Parser) and 2 different code generators as back end. The code generators are not needed for you task, you can directly evaluate while reducing.

But, for such an easy grammar, you do not need a stack at all. In the book crafting A Compiler with C is a good example. My copy of the book is from 1991, but of course the content is still valid.

They basically write a function for each production/terminal/non-terminal in the grammar and evaluate the tokens and call the functions of other terminals or non-terminals. Interesting approach and not difficult for your use case.

Hope this helps a little . . .

Upvotes: 4

Related Questions