Introduction to Stacks
- Due Sep 30, 2019 by 10pm
- Points 0
- Submitting a file upload
- File Types cpp
Description
This lab is designed to build and use a stack to solve a problem in computer science called parsing. Whenever a program like a compiler reads an input file, it must determine whether the file conforms to specific rules about what is "legal" input. Parsing the input is the process of determining the legality of input.
For this lab, we are only looking at one aspect of legal input: ensuring that paired delimiters match. A paired delimiter is a character that has a beginning, or opening, that matches an ending, or closing character. For example, parentheses have an opening "(" and closing ")". The paired delimiters we will check for in our program are:
- parentheses ()
- square brackets []
- curly brackets {}
- angle brackets <>
- single quotes `'
Algorithm
Your program will use a stack to perform the check to see if the delimiters match by using the following algorithm:
- read the next character (c) of the input
- if the character is an opening delimiter
- push the character on the stack
- if the character is a closing delimiter
- pop the top character (t) from the stack
- if c and t do not match
- display error message
- return to step #1 until input line is read completely
- if stack still contains delimiters,
- print error message
- if stack is empty,
- print success message
- return to step #1 with empty stack to read next input line
Examples
Your program should read in a line of input and indicate whether the line has properly matched the delimiters in the line. Correct lines should produce the output
SUCCESS
but invalid lines should produce the output
INVALID
<input line>
<error indicator>
The error indicator is designed to show where in the input line an invalid input exists. Here are three example error outputs.
INVALID
a[i] = f(a[i-1]
^
The above error shows an example when an opening delimiter does not have a matching closing delimiter.
INVALID
a[i] = f(a[i-1)]
^ ^
The above error shows an example when an opening delimiter does not match the closing delimiter.
INVALID
a[i] = f a[i-1])
^
The above error shows an example when a closing delimiter does not have a matching open delimiter.
Requirements
- For this lab, you must use a linked version of the stack like we began developing in class together. You may not use a vector or other built-in data structure provided by the C++ standard library.
- Your program should read lines from standard input until it detects the end of input.
- Each line is independent from each other and parsing one should not affect parsing another.
- No line will be longer than 1024 characters.