1. (5%) In the Knuth-Morris-Pratt string-pattern matching algorithm, we need a failure function. Compute the failure function for the following pattern.

3. (5%) Assume there are only variables such as a, b, c, and binary operators, such as t, -, *, and /in an arithmetic expression. The expression is fully parenthesized, that is, there is a pair of parentheses for each operator. Examples are (a+b)-c)/d), ((a+(c-(b-a))/d)+1), (((a+b)+c)+d)+e), etc. Write a program that translated a fully-parenthesized expression into its prefix form. The input is a correct, fully-parenthesized arithmetic expression, stored in a read-only array. This program can use 3queues together with the usual stack pointers. You cannot use additional storage, such as arrays, except a fixed number of simple temporary variables. In the program, you can only push, pop, examine the contents of a cell, and compare two contents of two cells for equality. The program can scan the input from left to right only once. It cannot store the input expression somewhere else for repeated examinations. You can use C or Java or Pascal or other similar programming languages to write this program. Your program should clearly show the underlying algorithm. Minor details and errors in the program will be tolerated. In particular you need to explain your data structures with examples.

1. (5%) In the Knuth-Morris-Pratt string-pattern matching algorithm, we need a failure function. Compute the failure function for the following pattern.

相關申論題

相關試卷