Infix expression evaluation [closed]

Question

I would like to evaluate(not convert) infix expression in C++. If you posses algorithm or even implementation of such algorithm(may be not C++, any language... I will try to rewrite it to C++) share please.

Evaluation means give the value of expression. (2+2)*3 is 12

I am sorry, I forgot that I am talking about stack solution, cause I know the tree solution and It is not suitable this time : (.

Answer 1

By far the easiest way is to convert the infix expression to postfix notation using Dijkstra's Shunting-yard algorithm, and evaulate the result, which is, like, trivial. There are code samples of this all over the internet (take a look at Rosetta code or LiteratePrograms).

---

Alternatively, if you'd like to learn, and you'd like to enter the magical world of parsing and a bit of compiler theory, write a recursive descent parser. It's great fun.

---

Oh and, if you'd like something more robust, you could take a look at Pratt parsing, which is awesome. Here's a great article about it.

Answer 2

How do you got the expression? If you got it like (3 + 4) - (1 * 2) + 1 =

                  +  
            /          \
           -            1
     /          \   
    +            *          
 /     \      /    \
3      4    1       2

http://cboard.cprogramming.com/cplusplus-programming/32682-inserting-infix-into-binary-tree.html

do a tree transversal of the tree like Left Root Right so it will be sth like this: 3 + 4 the result - the result of 1 * 2 the result + 1.

If you got the expression like 34+12*-1+ you can simulate assembly like do a stack and if you get to an operator pop the last 2 elements in the stack and apply the operator: put 3 in stack, put 4 in stack, get op. + so pop the last 2 elements and use the operator. Now you got only 7 in stack. Now read until get an operator so in the stack you will have 7 1 2 after op. * in stack you got 7 2 after op. - you get only 5 in stack add 1 in stack: Stack 5 1, use the last operator + and get the final result 6.

Ok, here is the code:

#include <STACK>

int GetResult( char * rpn ) 
{
    std::stack<int> myStack;

    int nr1, nr2; int length = strlen(rpn);

    for (int i = 0; i < length; i++)
    {
        if (isdigit(rpn[i]))
        {
            myStack.push(rpn[i] - '0');
        }
        else
        {
            switch(rpn[i])
            {
                case '+':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 + nr1);
                    break;

                case '-':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 - nr1);
                    break;

                case '*':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 * nr1);
                    break;

                case '/':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 / nr1);
                    break;
                default:
                    break;
            }
        }
    }

    return myStack.top();
}

int main(int argc, char* argv[])
{
    char *rpn = "34+12*-1+";

    int rez = GetResult(rpn);

    printf("%i", rez);

    return 0;
}