I am trying to write a C program that will determine whether a string of characters from the set "(, ), {, }, [, ]" is well formed; that is, if the scope delimiters come in matching pairs, and are properly nested. I need some helpful hints to approach writing this program.
For example, this is a correctly formed string:
{{()[]}}
The input to the program is strings can be no more than 72 symbols from the above set of characters followed by a dollar sign '$'. (I can use '\n' to terminate the input string.) The input can be either from the terminal or from an input file; this is optional.
For each input string, the program must either state that the string is well formed or indicate the character position from the left where there is a mismatch. Here is what the output will look like for these input strings:
$ is OK.
()$ is OK.
()[]$ is OK.
{{()[]}}$ is OK.
([)]$ is NOT OK (at symbol 3)
([$ is NOT OK (at symbol 3)
()][$ is NOT OK (at symbol 3)
}$ is NOT OK (at symbol 1)
The algorithm is as follows:
Start with an empty stack.
For each input character,
if it is a left delimiter "{, (, ["
push it on the stack.
If it is a right delimiter "}, ), ]" it must the left
delimiter on top of the stack:
if the stack is empty,
the string is bad already;
if the stack isn't empty,
pop and check the popped character
and the input character for a match.
If no mismatches occur before the end of the input string and the
stack is empty when the '$' is encountered, the string is well formed.
The algorithm needs to use the following stack operations :
void Push(StackEntry item, Stack *s)
void Pop(StackEntry *item, Stack *s)
Boolean StackEmpty(Stack *s)
Boolean StackFull(Stack *s) /* if needed */
void CreateStack(Stack *s)
These functions are provided in two other programs.
Follow this structure EXACTLY:
Implement the delimiter-checking algorithm as a function called DelimCheck which checks a string passed to it as a parameter.
Write a main program that contains a loop which reads and echo prints one line of input, calls DelimCheck, and prints the results.
The loop ends when there are no more input lines.
The printing of the final results of the check cannot be inside DelimCheck. The printing must be done either in the main routine or in a function called by the main routine.
Remember to comply with the firewall principle of using an abstract data type; that is, use the routines in your program in such a way that the application program does not access the stack in any way other than through the operations.
Thanks.
