evaluate infix expressions, shunting yard approach,.

evalinfix.cpp

class Evaluate {
private:
    template <class T>
    struct Stack : public stack<T> {
        T pop() {
            T ret = stack<T>::top();
            stack<T>::pop();
            //cout<<"Pop: "<<ret<<endl;
            return ret;
        }
        void push(T info) {
            //cout<<"Push: "<<info<<endl;
            stack<T>::push(info);
        }
    };
    Stack<int> sf;
    string in2post(string in) {
        Stack<char> op;
        string post;
        char r;
        for (char c : in) {
            if (c == '(') op.push(c);
            else if (c == '*' || c == '+' || c == '-' || c == '/')
                op.push(c);
            else if (c == ')') {
                while (!op.empty()) {
                    r = op.pop();
                    if (r == '(') 
                        break;
                    post.push_back(r);
                }
            } else {
                post.push_back(c);
            }
        }
        if (!op.empty())
            post.push_back(op.pop());
        return post;
    }

    int evalRPN(string post) {
        for (int i = 0; i < post.length(); i++) {
            char token = post[i];
            if (isdigit(token)) {
                string num;
                while (isdigit(post[i])) {
                    num.push_back(post[i++]);
                }
                i--;
                sf.push(atoi(num.c_str()));
            } else if (token == '+') {
                int v = sf.pop();
                int u = sf.pop();
                sf.push(u + v);
            } else if (token == '*') {
                int v = sf.pop();
                int u = sf.pop();
                sf.push(u * v);
            } else if (token == '-') {
                int v = sf.pop();
                int u = sf.pop();
                sf.push(u - v);
            } else if (token == '/') {
                int v= sf.pop();
                int u = sf.pop();
                sf.push(u / v);
            }
        }
        return sf.pop();
    }
    public:

    //shunting yard algorithm to convert infix to postfix
    //then evaluates as RPN
    int eval(string expr) {
        cout<<"EVal: "<<expr<<endl;
        string post = in2post(expr);
        cout<<"2post: "<<post<<endl;
        return evalRPN(post);
    }

};