## Chapter 7

7.2 Stack Applications

<1> example : Balanced Parenthese

```

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

action

( (  ) )

stack stores "(" only

"(" -> push "("

")" -> pop  "("```

<2>example evaluating anthemetic expressions

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

number is non-negative
every operation requires two arguments surrounding
with pair of matched parenthese
design
( ( (6+9)/3) * (6-4) )

by hand

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

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

evaluate the leftmost of the innermost expression

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

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

(5 * 2)
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

two stacks

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

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

( 5 * ( 6 - 4) )
=>

( 5 * 2 )
=>

=>

Summary
number stack store number

operation stack store operator

")" trigger the evaluation

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

")" or " " nothing happened```
``` Implementaton
Some functions in istream class
peek() return the next char of the istream var
ignore() discards the next char of input stream others
bool isdigit (char C) in ctype.h
true if '0'<<<'9'
false otherwise

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

Testing and Analysis
```