#include <iostream>
#include <conio.h>
using namespace std;

template <class type> struct Node {
    type data;
    Node* link;

    Node(type x)
    {
	data = x;
	link = NULL;
    }
};

template <class T> class Stack
{
private:
    Node<T>* top;

public:
    Stack()
    {
	top = NULL;
    }

    void push(T x)
    {
	Node<T>* temp = new Node<T>(x);

	if(top == NULL)
	    top = temp;
	else {
	    temp->link = top;
	    top = temp;
	}
    }

    bool pop(T& x)
    {
	if(top == NULL)
	    return false;
	else {
	    x = top->data;
	    Node<T>* temp = top;
	    top = top->link;
	    delete temp;
	    return true;
	}
    }

    bool peek(T& x)
    {
	if(top == NULL)
	    return false;
	else {
	    x = top->data;
	    return true;
	}
    }

    void print()
    {
	Stack<T> s;
	T k;

	while(pop(k)) {
	    cout << k;
	    s.push(k);
	}

	while(s.pop(k))
	    push(k);
    }

    ~Stack()
    {
	T k;
	while(pop(k))
	    ;
    }
};

class ConverterSolver
{
private:
    char* postfix;
    int postfixSize;
    char* variables;
    int varNum;
    double* varValue;

    bool isHigher(char a, char b)
    {
	int x, y;

	if(a == '(')
	    return false;

	if((a == '+') || (a == '-'))
	    x = 1;
	else
	    x = 2;

	if((b == '+') || (b == '-'))
	    y = 1;
	else
	    y = 2;

	return (x >= y);
    }

public:
    ConverterSolver(char A[], int e)
    {
	postfixSize = 0;
	varNum = 0;
	postfix = new char[e];
	variables = new char[e];
	varValue = new double[e];
	Stack<char> op;
	char cur, temp;
	bool found;

	for(int i = 0; i < e; i++) {
	    cur = A[i];

	    // Tracing ///////////////
	    cout << "cur: " << cur << endl;
	    /////////////////////////////

	    switch(cur) {

	    case '(':
		op.push(cur);
		break;

	    case '+':
	    case '-':
	    case '*':
	    case '/':
		if(op.peek(temp))
		    while(isHigher(temp, cur)) {
			op.pop(temp);
			postfix[postfixSize++] = temp;
			if(!op.peek(temp))
			    break;
		    }

		op.push(cur);
		break;

	    case ')':
		op.peek(temp);
		while(temp != '(') {
		    op.pop(temp);
		    postfix[postfixSize++] = temp;
		    op.peek(temp);
		}
		op.pop(temp);
		break;

	    default:
		postfix[postfixSize++] = cur;

		found = false;

		for(int u = 0; u < varNum; u++)
		    if(cur == variables[u])
			found = true;

		if(!found)
		    variables[varNum++] = cur;

		break;
	    }

	    // Tracing ///////////////

	    cout << "stack: ";
	    op.print();

	    cout << "\npostfix: ";

	    for(int h = 0; h < postfixSize; h++)
		cout << postfix[h];

	    cout << "\n\n";
	    //////////////////////////
	}

	while(op.pop(temp))
	    postfix[postfixSize++] = temp;

	postfix[postfixSize] = '\0';
    }

    void printPostfix()
    {
	cout << "Postfix results: " << postfix << endl;
    }

    void solvePostFix()
    {
	int i, count = 0;
	char cur;
	double x, y, z;

	cout << "Enter the corresponding values for each of the following variable: \n";

	for(i = 0; i < varNum; i++) {
	    cout << variables[i] << " = ";
	    cin >> varValue[i];
	}

	Stack<double> ans;

	for(i = 0; i < postfixSize; i++) {
	    cur = postfix[i];

	    switch(cur) {
	    case '+':
	    case '-':
	    case '*':
	    case '/':
		ans.pop(y);
		ans.pop(x);

		if(cur == '+')
		    z = x + y;
		else if(cur == '-')
		    z = x - y;
		else if(cur == '*')
		    z = x * y;
		else
		    z = x / y;

		ans.push(z);
		break;

	    default:
		ans.push(varValue[count++]);
	    }
	}

	ans.pop(z);

	cout << "The result of the calculation is: " << z << endl;
    }

    ~ConverterSolver()
    {
	delete[] postfix;
	delete[] variables;
	delete[] varValue;
	postfix = variables = NULL;
	varValue = NULL;
    }
};

int main()
{
    char c;
    char infix[100];
    int size = 0;

    cout << "Enter an infix expression with (?) at the end: \n";
    cin >> c;

    while(c != '?') {
	infix[size++] = c;
	cin >> c;
    }

    ConverterSolver k(infix, size);

    k.printPostfix();

    /*
      Example:  A+B*C-D/E? 
    */

    k.solvePostFix();

    cout << "\n\n";
    getch();
    return 0;
}

 OUTPUT:


Enter an infix expression with (?) at the end:
A+B*C-D/E?
cur: A
stack:
postfix: A

cur: +
stack: +
postfix: A

cur: B
stack: +
postfix: AB

cur: *
stack: *+
postfix: AB

cur: C
stack: *+
postfix: ABC

cur: -
stack: -
postfix: ABC*+

cur: D
stack: -
postfix: ABC*+D

cur: /
stack: /-
postfix: ABC*+D

cur: E
stack: /-
postfix: ABC*+DE

Postfix results: ABC*+DE/-
Enter the corresponding values for each of the following variable:
A = 2
B = 3
C = 4
D = 8
E = 3
The result of the calculation is: 11.3333