Application using Stack

/* C++ implementation to convert infix expression to postfix*/

#include
using namespace std;

//Function to return precedence of operators

int prec(char c)
{
    if(c == '^')
    return 3;
    else if(c == '*' || c == '/')
    return 2;
    else if(c == '+' || c == '-')
    return 1;
    else
    return -1;
}
// The main function to convert infix expression
//to postfix expression

void infixToPostfix(string st)
{
 stack s;
 clear(s);
 int length = st.length();
 string ns;
 for(int i = 0; i < length; i++)
 {
  //If the scanned character is an operand, add it to output string.
  if((st[i] >= 'a' && st[i] <= 'z')||
     (st[i] >= 'A' && st[i] <= 'Z'))
        ns+=st[i];

   // If the scanned character is an ‘(‘, push it to the stack.
        else if(st[i] == '(')

        push(s,'(');

   // If the scanned character is an ‘)’, pop and to output string from the stack
        // until an ‘(‘ is encountered.
        else if(st[i] == ')')
        {
            while(!empty(s) && stacktop(s) != '(')
            {char c = pop(s);
             ns += c;}
            if(stacktop(s) == '(')
              char c = pop(s);
        }
        //If an operator is scanned
        else {
               while(!empty(s) &&
                     prec(st[i]) <= prec(stacktop(s)))
                 {char c = pop(s);
                  ns += c;}
               push(s, st[i]);
        }
      }
    //Pop all the remaining elements from the stack
    while(!empty(s))
      {char c = pop(s);
        ns += c;}
    cout << ns << endl;
}
//Driver program to test above functions
int main()
{
    string exp = "a+b*(c^d-e)^(f+g*h)-i";
    infixToPostfix(exp);
}


Evaluation of Postfix Expression

// C++ program to evaluate value of a postfix expression
#include <iostream>
#include <string.h>
 using namespace std;
// The main function that returns value of a given postfix expression
int evaluatePostfix(char* exp)
{
  int i;
  stack s;
    // Scan all characters one by one
    for (i = 0; exp[i]; ++i)
    {  // If the scanned character is an operand (number here),  push it to the stack.
       if (isdigit(exp[i]))
            push(stack, exp[i] - '0');
       // If the scanned character is an operator, pop two
      // elements from stack apply the operator
        else
        {
            int val1 = pop(stack);
            int val2 = pop(stack);
            switch (exp[i])
            {
            case '+': push(stack, val2 + val1); break;
            case '-': push(stack, val2 - val1); break;
            case '*': push(stack, val2 * val1); break;
            case '/': push(stack, val2/val1); break;
            }
        }
    }
    return pop(stack);
}

// Driver program to test above functions
int main()
{   char exp[] = "231*+9-";
    cout<<"postfix evaluation: "<< evaluatePostfix(exp);
}
Output:  postfix evaluation: -4

There are following limitations of above implementation.
1) It supports only 4 binary operators ‘+’, ‘*’, ‘-‘ and ‘/’.
   It can be extended for more operators by adding more switch cases.
2) The allowed operands are only single digit operands. The program
   can be extended for multiple digits by adding a separator like
   space between all elements (operators and operands) of given expression.
// The main function that returns value  of a given postfix expression
int evaluatePostfix(char* exp)
{  for (i = 0; exp[i]; ++i)   // Scan all characters one by one
    {         //if the character is blank space then continue
        if(exp[i] == ' ') continue;
    // If the scanned character is an operand (number here),extract the full number
        // Push it to the stack.
        else if (isdigit(exp[i]))
        {
            int num=0;
            //extract full number
            while(isdigit(exp[i]))
            {   num = num * 10 + (int)(exp[i] - '0');
                i++;
            }
            i--;
            //push the element in the stack
            push(stack,num);
        }
        // If the scanned character is an operator, pop two
        // elements from stack apply the operator
        else
        {
            int val1 = pop(stack);
            int val2 = pop(stack);
            switch (exp[i])
            {          case '+': push(stack, val2 + val1); break;
                case '-': push(stack, val2 - val1); break;
                case '*': push(stack, val2 * val1); break;
                case '/': push(stack, val2/val1); break;
            }
        }
    }
    return pop(stack);
}