In this assignment, you will implement a program that checks a list of string expressions given in a text file, if they have balanced parenthesis and brackets using a stack data structure. In a balanced expression, every open parenthesis (or bracket) is matched with a corresponding close parenthesis (or bracket), and they are properly nested. An expression can be long or short, but only three types of parenthesis or brackets will be considered such as (), [], and {}. The expression may also have some random characters, but they should simply be ignored. For example:

{{[a]b}[]([c])}

is a perfectly balanced expression, because all parenthesis and brackets are matching. Every opening parenthesis has a corresponding closing parenthesis. For this expression, your program should print a message stating the expression is balanced. Another example could be

[]}b[]([])(}[

which is a not a balanced expression because not all parentheses are matching. In this case, your program will print a message stating the expression is not balanced.

Your program will read a text file called input.txt including a list of expressions (one expression in one line). Some of those expressions have balanced parenthesis, and some do not. Your program should check all expressions in a loop and print the corresponding message for each of them.

In your program, please use the stack library (#include ) provided in C++. You can find details of that library and some example codes at

http://www.cplusplus.com/reference/stack/stack/push/ (Links to an external site.)

You will submit one cpp file including your solution. I provide a reference input.txt file for you to test your program. But I can test your program with different files including different expressions.

input.txt

{{[a]b}[]([c])}

[]}b[]([])(}[

[][[{a}{b}{c}]]

({{[x]}([[[[[a]]]b]])c}[])

{{{{{{{{{a}}}}}}}}{[}]

[[}[abc]{]]

[{{}()()([])}[}]]

{a}{{[a[[{(a)}]]]}}

[[({a[]})b]{}[({c[]}d)]]