Stack - for Computer Science and MCA students

Write a program to check nesting of parentheses using stack.

#include<iostream.h>
using namespace std;
#define MAX 40
classCheckExpression
{
     int stack[MAX];
     int n, top;
public:
     CheckExpression()
     {
          top = -1;
     }
     int matchParenthesis(char a, char b)
     {
          if(a=='['&& b==']')
               return 1;
          if(a=='{'&& b=='}')
               return 1;
          if(a=='('&& b==')')
               return 1;
     return 0;
     } /*End of matchParenthesis()*/
void push(char item)
{
     if(top==(MAX-1))
     {
          cout<<"Stack is Overflow\n";
          return;
     }
     top = top + 1;
     stack[top] = item;
} /*End of push()*/
char pop()
{
     if(top==-1)
     {
          cout<<"Stack is Underflow\n";
          exit(1);
     }
     return(stack[top--]);
} /*End of pop()*/
     int check(charexp[])
     {
          int i;
          char temp;
          for(i = 0; i<strlen(exp); i++)
          {
               if(exp[i]=='(' || exp[i]=='{' || exp[i]=='[')
               push(exp[i]);
               if(exp[i]==')' || exp[i]=='}' || exp[i]==']')
               if(top==-1) /*stack is empty*/
               {
                    cout<<"Right parentheses are more than left parentheses\n";
                    return 0;
               }
               else
               {
                    temp = pop();
                    if (!matchParenthesis(temp, exp[i]))
                    {
                         cout<<"Mismatched parentheses are : ";
                         cout<<temp<<" "<<exp[i];
                         return 0;
                    }
               }
          }
               if(top==-1) /*stack empty*/
               {
                    cout<<" Parentheses are Balanced\n";
                    return 1;
               }
               else
               {
                    cout<<"Left parentheses more than right parentheses\n";
                    return 0;
               }
     }
};
void main()
{
     CheckExpressionobj;
     intvalidExp;
     charexp[30];
     cout<<"Enter the expression \t"<<endl;
     cin>>exp;
     validExp=obj.check(exp);
     if(validExp==1)
          cout<<"Valid expression\n";
     else
          cout<<"Invalid expression\n";
}

Convert given postfix expression into prefix expression and give stack trace.

A B C D ^ ^ E F G - * H I / * / + J *
InputActionPrefix Expression
APush into the stackA
BPush into the stackA, B
CPush into the stackA, B, C
DPush into the stackA, B, C, D
^Pop
two elements and append operator as prefix and push expression back into stack.
A, B, ^CD
^Pop two elements and append operator as prefix and push expression back into stack.A, ^B^CD
EPush into the stackA, ^B^CD, E
FPush into the stackA, ^B^CD, E, F
GPush into the stackA, ^B^CD, E, F, G
-Pop two elements and append operator as prefix and push expression back into stack.A, ^B^CD, E, -FG
*Pop two elements and append operator as prefix and push expression back into stack.A, ^B^CD, *E-FG
HPush into the stackA, ^B^CD, *E-FG, H
IPush into the stackA, ^B^CD, *E-FG, H, I
/Pop two elements and append operator as prefix and push expression back into stack.A, ^B^CD, *E-FG, /HI
*Pop two elements and append operator as prefix and push expression back into stack.A, ^B^CD, **E-FG/HI
/Pop two elements and append operator as prefix and push expression back into stack.A, /^B^CD**E-FG/HI
+Pop two elements and append operator as prefix and push expression back into stack.+A /^B^CD**E-FG/HI
JPush into the stack+A /^B^CD**E-FG/HI, J
*Pop two elements and append operator as prefix and push expression back into stack.*+A /^B^CD**E-FG/HIJ
Prefix Expression is => *+A /^B^CD**E-FG/HIJ

Convert infix to postfix form. Represent operator in stack and expression at each step.
P * (Q + R ^ S) – T ^ U * (V/W)

Solution:
InputOperator in stackPostfix Expression
PEmptyP
**P
(*, (P
Q*, (PQ
+*, (, +PQ
R*, (, +PQR
^*, (, +, ^PQR
S*, (, +, ^PQRS
)*PQRS^ +
--PQRS^+*
T-PQRS^ +*T
^-^PQRS^+*T
U-, ^PQRS^ +*TU
*-, *PQRS^+*TU
(-, *PQRS^+*TU^
V-, *PQRS^+*TU^V
/-, /PQRS^+*TU^V*
W-, /PQRS^+*TU^V*W
)PQRS^+*TU^V*W–/

Hence the postfix expression is : PQRS^+*TU^V*W–/