"Warmup" Programming Assignments: (L)L
Parse a simple language. Write a program to accept or reject strings in the language with the following production rules.
- L -> (L)L
L -> lambda
(lambda means the empty string)
- Examples:
- () accepts
- ()) rejects
- (()) accepts
- (())() accepts
- ((()))(())() accepts
- ((()))(())()) rejects
- empty string accepts
Your program should keep accepting input until a 'q' is typed, for example.
Hand in:
- Example output, fully tested with various kinds of test cases
(to save output: highlight the output, press both mouse buttons in an editor. This should paste)
- Prose description of your algorithm, your approach to solving the problem.Use code excerpts if necessary.
Suggested algorithm to use:
- If you read open paren, put this on the stack. i.e. only put open parens on the stack.
- When you read a close paren, pop an open paren off the stack.
- There should always be a matching open paren on the stack for each close paren in the input.
- At the end of the input, the stack of open parens should be empty.