Midterm Examination Solutions Winter 2005

PwnHero Ryerson University Department of Electrical & Computer Engineering ELE428 ^ d^ Midterm Examination March, 04, 2005 Name: (VI^K^v^r^^cl P?^uj0\?\ Section: _ ID#: Time: 50 min. Examiner: K. Clowes, M. Jaseemuddin, R. Sedaghat Write your name on each page. Pages without a name will not be graded. Answer all of the following questions in the space provided. Closed book. No Calculator, No questions 1) Use the standard "Balance" algorithm to determine if the following expressions are balanced. (The standard "Balance" algorithm assumes that the input is a sequence of start-tags and end-tags. Each tag is processed sequentially and a Stack push or pop operation is performed. Here, start-tags are lower-case letters and end-tags are upper-case letters. For example, "aA" balances but "aB" does not balance.) The standard algorithm processes each tag until: It encounters an error or the input sequence ends. For each sequence below, show how the stack evolves as each tag is processed. If an error occurs, stop processing and indicate the type of error. (Note: assume the stack has unlimited capacity so an overflow cannot occur; underflow errors, however, can happen.) a) aaAbBA b) aaabbBABAA c) abBbaABABa PwnHero.com