Infix-Posfix-Evaluate

#include <iostream>
#include <sstream>
#include <cstdlib>
#include <cmath>
using namespace std ;

string convStr(char ch) {
    string line = "";
    line += ch;
    return line;
}

string clrstr(string str) {
    string out = "";
    for (int i = 0, j = -1; str[i]; i++) {
        if (str[i] != ' ') {
            out += convStr(str[i]);
            j++;
        }
        else
            if (out[j] != ' ') {
                out += " ";
                j++;
            }
    }
    return out;
}

template <class T>
class myStack {
private:
    T data;
    myStack *next;

public:
    myStack(T x, myStack *n): data(x), next(n) {}
    myStack(): next(NULL) {}

    void push(T x) {
        next = new myStack(x, next);
    }

    bool pop() {
        if (next != NULL) {
            myStack *D = next;
            next = next -> next;
            delete D;
            return true;
        }
        else return false;
    }

    T top() {
        if (next != NULL)
            return next -> data;
    }

    int count() {
        int i = 0;
        for (myStack *cur = next; cur != NULL; cur = cur -> next)
            i++;
        return i;
    }

    void display() {
        if (next != NULL)
            for (myStack *cur = next; cur != NULL; cur = cur -> next)
                cout << cur -> data << " ";
        else
            cout << "< empty >";

        cout << endl;
    }

    bool empty() {
        return bool(next);
    }

    void sort() {
        if (next != NULL)
            for (myStack *prev = next; prev -> next != NULL; prev = prev -> next)
                for (myStack *cur = prev -> next; cur != NULL; cur = cur -> next)
                    if(prev -> data > cur -> data)
                        swap(prev -> data, cur -> data);
    }
};

void pop(double &first, double &second, myStack <double> &S) {
    second = S.top();
    S.pop();
    first = S.top();
    S.pop();
}

int main() {
    myStack <char> S;
    char ch;
    string line, str;
    string postfix = "";

    cout << "Enter the Infix Expression (with parenthesis): ";
    getline(cin, line);

    for (int i = 0; line[i]; i++) {
        if (line[i] == ' ')
            postfix += " ";
        else if (line[i] == '(' || line[i] == '+' || line[i] == '-' || line[i] == '*' || line[i] == '/' || line[i] == '%' || line[i] == '^')
            S.push(line[i]);
        else if (line[i] == ')') {
            while (S.top() != '(') {
                postfix += " " + convStr(S.top()) + " ";
                S.pop();
            }
            S.pop();
        }
        else
            postfix += line[i];
    }

    postfix = clrstr(postfix);
    cout << "Postfix: " << postfix << endl;

    //Evaluate
    istringstream inpstr(postfix);
    myStack <double> Sr;
    double first, second;

        while(inpstr >> str) {
            if(str == "+") {
                pop(first, second, Sr);
                Sr.push(first + second);
            }
            else if(str == "-") {
                pop(first, second, Sr);
                Sr.push(first - second);
            }
            else if(str == "*") {
                pop(first, second, Sr);
                Sr.push(first * second);
            }
            else if(str == "/") {
                pop(first, second, Sr);
                Sr.push(first / second);
            }
            else if(str == "^") {
                pop(first, second, Sr);
                Sr.push(pow(first, second));
            }
            else
                Sr.push(strtof(str.c_str(), NULL)); //str.c_str() returns a C-String eqv of the String type object
        }
        cout << "Value of the expression is: " << Sr.top() << endl;

    return 0;
}