evaluate_postfix.cpp

/*
 Author : Sarthak Saxena (Sarthak-9).
 Program to evaluate PostFix Expression.Postfix is an arithmetic expression
 in which we place the operator after two operands. It has various applications.
 Time Complexity: O(n)
 Space complexity: O(n)
 where n is the number of characters input in expression.
*/

#include <iostream>
#include <stack>

using namespace std;

class Node{
public:
        int data;
        Node* next;
};

class Stack{
private:
        Node* top;
public:
        Stack();
        ~Stack();
        void push(int x);
        int pop();
        int peek(int index);
        int isEmpty();
        int isFull();
        int stackTop();
};

Stack::Stack() {
        top = nullptr;
}

Stack::~Stack() {
        Node* p = top;
        while (top){
                top = top->next;
                delete p;
                p = top;
        }
}

void Stack::push(int x) {
        Node* t = new Node;
        if (t == nullptr){
                cout << "Stack Overflow!" << endl;
        } else {
                t->data = x;
                t->next = top;
                top = t;
        }
}

int Stack::pop() {
        Node* p;
        int x = -1;
        if (top == nullptr){
                cout << "Stack Underflow!" << endl;
        } else {
                p = top;
                x = p->data;
                top = top->next;
                delete p;
        }
        return x;
}

int Stack::isFull() {
        Node* t = new Node;
        int r = t ? 1 : 0;
        delete t;
        return r;
}

int Stack::isEmpty() {
        return top ? 0 : 1;
}

int Stack::stackTop() {
        if (top){
                return top->data;
        }
        return -1;
}

int Stack::peek(int index) {
        if (isEmpty()){
                return -1;
        } else {
                Node* p = top;

                for (int i=0; p != nullptr && i<index-1; i++){
                    p = p->next;
                }

                if (p != nullptr){
                    return p->data;
                } else {
                    return -1;
                }
        }
}


int isOperand(char x){
        if (x == '+' || x == '-' || x == '*' || x == '/'){
                return 0;
        }
        return 1;
}

int operation(char op, int x, int y){
        if (op == '+'){
                return x + y;
        } else if (op == '-'){
                return x - y;
        } else if (op == '*'){
                return x * y;
        } else if (op == '/'){
                return x / y;
        }
}

int postfixEvaluate(char* postfix){
        stack<int> stk;
        int x;
        int y;
        int result;
        for (int i=0; postfix[i]!='\0'; i++){
                if (isOperand(postfix[i])){
                        stk.push(postfix[i]-'0');
                } else {
                        y = stk.top();
                        stk.pop();
                        x = stk.top();
                        stk.pop();
                        result = operation(postfix[i], x, y);
                        stk.push(result);
                }
        }
        result = stk.top();
        stk.pop();
        return result;
}

int Evaluate(char* postfix){
        Stack stk;
        int x;
        int y;
        int result;
        for (int i=0; postfix[i]!='\0'; i++){
                if (isOperand(postfix[i])){
                        stk.push(postfix[i]-'0');
                } else {
                        y = stk.pop();
                        x = stk.pop();
                        result = operation(postfix[i], x, y);
                        stk.push(result);
                }
        }
        result = stk.pop();
        return result;
}

int main() {

        char postfix[100];
        cout <<"Enter the expression"<<endl;
        cin>>postfix;
        cout <<"The evaluated answer from Method 1 : "<< Evaluate(postfix) << endl;
        cout <<"The evaluated answer from Method 2 : "<< postfixEvaluate(postfix) << endl;

        return 0;
}

/*
 Input :
 Enter the expression
 35*62/+4-

 Output :
 The evaluated answer from Method 1 : 14
 The evaluated answer from Method 2 : 14
 */