Chapter 7

7.2 Stack Applications

<1> example : Balanced Parenthese

    


  1.  is_balanced function (page 312)
    

 bool is_balanced( const String & expression) ;
    

eg
    

   is_balanced("(3+a-(b+7))") => true

   is_balanced("((x+y*(z+1)*(a+b))") =>false
    


  2.  action
      


    1.  ( (  ) )
        


      1. 


      2. 


      3. 


      4. 


      5. 



      

stack stores "(" only

     "(" -> push "("

     ")" -> pop  "("


<2>example evaluating anthemetic expressions 

    

  1.  specification
     ( ( ( (12+9)/3)+7.2)*( (6-4)/8) )

      

    1.  number is non-negative

    2.  every operation requires two arguments surrounding 
  with pair of matched parenthese
    

  2.  design
     ( ( (6+9)/3) * (6-4) )

      

    1.  by hand

   ( ( (6+9) /3 ) * (6-4) )
        ~~~          ~~~
         15           2

=> ( (15/3) * 2 ) => (5*2) => 10


    2.  evaluate the leftmost of the innermost expression

        

      1.  ( ( (6+9) /3 ) * (6-4) )

      2.  ( ( 15/3 ) * (6 -4 ) )
     ~~~~
      5


      3.  ( 5 * (6-4) )
        ~~~
         2


      4.  (5 * 2)

      5.  10
    
 Note :

Q : How to find the leftmost of the innermost expression ?

A : Find the ")"

Q : How to keep track of volues and operator ?

A : Use two stacks
        one for numbers
        one for operator
eg

 => 3+5



  3.  two stacks

   ( ( ( 6 + 9 ) / 3 ) * ( 6 - 4 ) )
        ~~~~~~~

      

    1. 

( ( 15 /3 ) * ( 6 -4 ) )
=>


    2. 

( 5 * ( 6 - 4) )
=>


    3. 

( 5 * 2 )
=>


    4. =>

    


Summary
      

    1. number stack store number


    2. operation stack store operator


    3.  ")" trigger the evaluation

        => pop two numbers from number stack
           pop operator from operation stack
           push the result to number stack


    4.  ")" or " " nothing happened
  4.  Implementaton 
  Some functions in istream class
      

    1.  peek() return the next char of the istream var
        without actually reading it 

    2.  ignore() discards the next char of input stream others

    3.  bool isdigit (char C) in ctype.h
         true if '0'<<<'9'
         false otherwise



    4.  char*  strchr (const char s[] char C)
                                   in string.h
 check if C is in s[]
   it yes then returns a printer to the first
     occurrence of C in S
    no then return NULL
    


  5.  Testing and Analysis