Stack

Stack is list accessed and stored in a LIFO (last in first out) technique. In stack, insertion and deletion take place only at one end, called the top.

For eg. Stack of plates.

Stack in C++

Stack Operation

Stack as an array

°       Push (insertion in a stack as an array)

int push(int stack[], int &top, int ele)

{

  if(top==size-1)    return -1;

  else

  {

    top++;

    stack[top]=ele;

  }

}

Display Stack-

void display( int stack[], int top)

{

  cout<<stack [top] <<” <-”<< endl;

  for (i=top-1; i>=0; i--)

      cout<<stack[i]<<endl;

°        Pop (deletion of element from stack)

int pop(int[] ,int&)

{

  int ret;

  if(top==-1)        return -1;

  else

  {

    ret =stack[top];

top --;

}

Conversion of Infix Expression to postfix-

Rule-

I.                  Brackets or parenthesis

II.               Exponentiation

III.           Multiplication or division

IV.            Addition or Subtraction

Q. Convert (A+B)xC/D into postfix.

 

Sol.                        [A+BxC]/D

                            = [(AB+)Cx]/D

                            =    AB+CxD

Q. Convert into postfix -A*(B+(C+D)*(E+F)/G)*H

Sol. Convert expression into braces-

        (A*(B+ [(C+D)*(E+F)]/G)*H

      =A*(B+ [(CD+)*(EF+)/G])*H

      = (A*(B+ ((CD+EF+*)/G))*H

      = (A*(B+ (CD+EF+*G/))*H

      =A*(BCD+EF+*G/+)*H

      =ABCD+EF+*G/+*H*

Q. Convert into postfix-   A+ [(B+C) + (D+E)*F]/G

  

Sol.

Convert exp into braces-

= A + ([(B+C) + ((D+E)*F)]/G)

= A + ([(BC+) + ((DE+)*F)]/G)

= A + ([(BC+)+(DE+F*)]/G)

=A + (BC+DE+F*+)/G

=A + (BC+DE+F*+G/)

=ABC+DE+F*+G/+

Evaluation

Method 1

Q. Evaluate the postfix expression AB +C xD/ if A=2, B=3, C=4 and D=5 and showing contents of stack.

Sol. Expression AB + C* D/

Method 2- Showing stack status

Q. Evaluate the expression  562 + * 124/- in tabular form showing stack status after every step.

Sol.

Step     Input Symbol/                                Stack                  Intermediate-       
                Element                                                         calculation/output

1.             5                 push                           5                

2.             6                 push                          5,6

3 .            2                 push                          5,6,2

4.             +                pop(2elements)        5                             6+2=8

5.                                push result(8)          5,8

6.              *                pop (2 elements)      empty                     5*8=40

7.                                push result (40)       40 

8.             12               push                          40,12

9.              4               push                           40,12,4

10.            /                pop (2elements)        40                          12/4=3    

11.                              push result (3)           40,3

12.            -                pop (tow elements)    empty                  40-3=37    

13.                              push result (37)         37     

14.                              no more element                                      37(result)

Q. Evaluate the following postfix notation of exp-(show status of stack after each operation)

False, True, Not, OR, True, False, AND , OR

Sol. Step           Input Sym/                  Stack Status           Intermediate-

                     Element                                                        Cal/output

1.                   false        push                   false     

2.                   true         push               false, true  

3.                   Not          pop (1ele)          false                    Not true=false         

4.                                   push result     false,false

5.                   OR           pop (2ele)         empty               falseOR false=false

6.                                    push result         false

7.                 true            push                    false,true

8.                 false           push              false,true,false

9.                 AND          pop(2 ele)             false               trueANDfalse=false

10.                                  push(result)     false,false

11.               OR              pop(2 ele)         empty             falseORfalse=false  

12.                                   push result       false                false(result)     

                  

This post is about Stack in C++. In the next post we will discuss the topic Queue .