Outlines
•Arithmetic Expressions
•Polish Notation
•Evaluation of a Postfix Expression
•Transforming Infix expression to Postfix 
   Expression.


    Arithmetic Expressions
•Arithmetic Expressions involve constants and operations.

•Binary operations have different levels of precedence.
         –First    :   Exponentiation (^)
         –Second:  Multiplication (*) and Division (/)
          –Third   :  Addition (+) and Subtraction (-)
Stack and queue
                                 Example
•Evaluate the following Arithmetic Expression:
5 ^ 2 + 3 * 5 – 6 * 2 / 3 + 24 / 3 + 3
•First:
  25 + 3 * 5 – 6 * 2 / 3 + 24 / 3 + 3
•Second:
  25 + 15 – 4 + 8 + 3
•Third:
  47
Polish Notation
•Infix Notation: Operator symbol is placed between the two operands.

Example:

  (5 * 3) + 2         &   5 * (3 + 2)
   Polish Notation
qPolish Notation: The Operator Symbol is placed before its two operands.
  Example:   + A B, * C D, / P Q etc.
•Named after the Polish Mathematician Jan L..
•The order in which the operations are to be performed is 
completely determined by the positions of operators and 
operands in the expression.
                   Examples
•(A + B) * C = * + ABC
•A + (B * C) = + A *BC
•(A + B) / (C - D) = / +AB –CD
•Also Known as Prefix Notation.

Reverse Polish Notation

qReverse Polish Notation: The Operator Symbol is
placed after its two operands.
Example:    A B+, C D*,  P Q/ etc.
•Also known as Postfix Notation.

 Evaluation of Postfix Expression
qP is an arithmetic expression in Postfix Notation.
1.Add a right parenthesis “)” at the end of P. 
2.Scan P from left to right and Repeat Step 3 and 4 for
each element of P until the sentinel “)” is encountered.
3. If an operand is encountered, put it on STACK.
4. If an operator @ is encountered, then
       (A) Remove the two top elements of STACK, where
             A   is the top element and B is the next to top
              element.
       (B) Evaluate B @ A.
       (C) Place the result of (B) back on STACK.
             [End of if structure.]
           [End of step 2 Loop.]
  5.Set VALUE equal to the top element on STACK.
  6.Exit.

Infix to Postfix Transformation
  POLISH (Q, P)
1.PUSH “(” on to STACK and add “)” to the end of Q.
2.Scan Q from left to right and Repeat steps 3 to 6 for
each element of Q until the STACK is empty:
3.  If an operand is encountered, add it to P.
4.  If a left parenthesis is encountered, push it onto
STACK.
5.  If an operator @ is encountered, then:
 (a) Repeatedly POP from STACK and add to P each
operator (On         the TOP of STACK) which has the same
precedence as or         higher precedence than @.
(b) Add @ to STACK.
[End of If structure.]
6.If a right parenthesis is encountered, then:
 (a) Repeatedly POP from STACK and add to P each
operator (On the TOP of STACK.) until a left parenthesis
is encountered.
(b) Remove the left parenthesis. [Don’t add the left
parenthesis to P.] 
[End of If Structure]
 [End of step 2 Loop.]
7.    Exit.


Linklist implementation of stack

#include<iostream>

#include<stdio.h>

using namespace std;

struct node{

int info;

node *link;

}*start=NULL;


void push(int item)

{

node *temp=new node;

temp->info=item;

temp->link=start;

start=temp;

}

int peak()

{

node *ptr=start;

if(ptr==NULL)

{

return 0;

}

else

{

int it=ptr->info;

return it;

}

}

int pop()

{

node *ptr=start;

if(ptr==NULL)

{

return 0;

}

else

{

int i=ptr->info;

start=ptr->link;

return i;

}

}

void display()

{

node *ptr=start;

if(ptr==NULL)

{

cout<<"THere is nothing to display";

}

while(ptr!=NULL)

{

cout<<ptr->info<<"\t";

ptr=ptr->link;

}

}

int main()

{

int item,choice;

while(1)

{

cout<<"\n1. Push\n2. Pop\n3.Peak-value\n4 Display\n5. Exit";

cout<<"\nEnter your choice";

cin>>choice;

switch(choice)

{

case 1:

cout<<"Enter the value to be pushed";

cin>>item;

push(item);

break;

case 2:

    item=pop();

    if(item!=0)

    {

    cout<<"popped value is "<<item;

}

else

{

cout<<"stack is empty";

}

break;

case 3:

item=peak();

if(item==0)

{

cout<<"Stack is empty";

}

else

{

cout<<"peak value is "<<item;

}

break;

case 4:

display();

break;

case 5:

exit(0);

}

}

return 0;

}