1. Use the STL stack container in a program that reads a string, an arithmetic expression to be exact, one character at a time, and determines if the string contains balanced parenthesis – that is, for each left parenthesis (if there are any) there is exactly one matching right parenthesis later in the string.

Use the following strings to test your program.

1. A+ B- C

2. A * B / (C+10)

3. A * ((B / C) + D + (E-10)

4. A * (B / C) + D + (E-10))

Clearly describe the algorithm you will use to determine if the string contains balanced parenthesis. Document the program so I can follow what is going on. The output should look like this:

String: A + B – C No parenthesis

String: A * B / (C+10) Matching parenthesis

String: A * ((B / C) + D + (E-10) Parenthesis don’t match. Missing right parenthesis

String: A * (B / C) + D + (E-10)) Parenthesis don’t match. Missing left

parenthesis

[Hint: Read the expression left to right, one character at a time. If the character read is a left paren ‘(‘, Push the left paren onto the stack. If the character is a right paren ‘)’, pop the stack. If the character is neither, ignore the character. After all characters have been read, if the stack has left over parenthesis, the expression has unbalanced parenthesis, else the parenthesis are balanced.]