Python Assignment:

Think about the "Example Application: Matching Parentheses" section.

Write about the following: - the key reason the stack-based solution works - your evaluation of using a simple counter instead of a stack - your evaluation of using a queue instead of a stack - the importance of using the right tool for a job - other insights you discovered

A minimum of 160 words please.

Example and etc.

Example Application: Matching Parentheses Compilers need to determine if the bracketing symbols in expressions are balanced correctly. For example, every opening [ should be followed by a properly positioned closing ] and every ( by a ).The table provides some examples.

In these examples, three dots represent arbitrary strings that contain no bracketing symbols.

As a first attempt at solving the problem of whether brackets balance, you might simply count the number of left and right parentheses. If the expression balances, the two counts are equal. However, the converse is not true. If the counts are equal, the brackets do not necessarily balance. The third example provides a counterexample.

A more sophisticated approach, using a stack, does work. To check an expression, take the following steps:

1. Scan across the expression, pushing opening brackets onto a stack.

2. On encountering a closing bracket, if the stack is empty or if the item on the top of the stack is not an opening bracket of the same type, you know the brackets do not balance, so you can quit the process and signal that the expression is improperly formed.

3. Otherwise, pop the item off the top of the stack and continue scanning the expression.

4. When you reach the end of the expression, the stack should be empty, and if it is not, you know the brackets do not balance.

Here is a Python script that implements this strategy for the two types of brackets mentioned. Assume that the module linkedstack includes the class LinkedStack.

"""

File: brackets.py

Checks expressions for matching brackets

"""

Code for brackets.py:

from linkedstack import LinkedStack def bracketsBalance(exp):

"""exp is a string that represents the expression"""

stk = LinkedStack() # Create a new stack

for ch in exp: # Scan across the expression

if ch in ['[', '(']: # Push an opening bracket

stk.push(ch)

Table below:

[(]) Unbalanced The bracketed sections are not nested properly