C++ ：CS2250 Delimiter MatchingHelp With Programming

Stack。

Description

In this project, we will solve a problem called Delimiter Matching using the stack data structure. The data structures are an important part of this class. We would like to experience the power of the data structures through this project.

An idea to solve this Delimiter Matching problem is given in our Lecture 10, Slide 5. After you completely understand that example and the basic operations of a stack, you are ready to work on this project.

In this project, our delimiters are defined in two categories: 1) the opening delimiters: {, [, ( and 2) the closing delimiters: }, ], ). When we process a string containing several delimiters, we want to check if the following rule is satisfied:

• When we go through the given string character by character, each opening delimiter should be matched by its corresponding closing delimiter before any other closing delimiter is encountered.

Requirements

1. (Input) When your program starts, it prompts the user to enter a string that contains certain number of the above delimiters. Then your program is going to check if our delimiter matching rule is satisfied.
2. (Dynamic Stack ) Since we do not know the number of characters in the given string, we should use a dynamic stack to do the processing. You have two ways to do it:
   • Convert the example on page 1183 from the int version to the char version, because we use the characters as our data.
   • You can also use the dynamic stack template example on page 1187. Then in your main function, you just pass char as your type parameter. Choose the one that is easier for you.
3. (Checking Delimiter Rule) Start a loop through all the characters in the given string from beginning to end. Then check the delimiter rule with the following steps:

• Every time when you see a non-delimiter character, skip it.
• When you see an opening delimiter, push it into the stack.
• When you see a closing delimiter, pop the stack and compare if the character received from the stack matches the current closing delimiter.
• If the opening delimiter popped out from the stack matches the current closing delimiter, there is no violation, and your program continues to process the next character.
• If the opening delimiter popped out from the stack does not match the current closing delimiter, you detect a rule violation. The current processing stops immediately with an error message.
• After you complete the whole string processing without any violation, you print out a message telling the user that the rule is satisfied for the input string. Then your program stops.