Background:
Let c0c1c2...cn
be a string, where each ci
is a character. Then its reverse is cncn-1...c2c1c0
.
Notice that the first character of the reverse is the last character of the original and that what follows it is the reverse of the string obtained by chopping off the last character of the original string. Combining this with the observation that the reverse of the empty string is itself, we surmise that
reverse(s) = { s if s has length 0
{ a + reverse(s') otherwise
where +
denotes concatenation, s'
denotes s
with its last character chopped off, and a
denotes the last character of s
.
Indeed, this recursive definition of reverse
corresponds to our intended meaning. For example, if we apply the definition to the string "abcde" we get:
reverse("abcde") = 'e' + reverse("abcd")
= 'e' + ('d' + reverse("abc"))
= 'e' + ('d' + ('c' + reverse("ab")))
= 'e' + ('d' + ('c' + ('b' + reverse("a"))))
= 'e' + ('d' + ('c' + ('b' + ('a' + reverse("")))))
= 'e' + ('d' + ('c' + ('b' + ('a' + ""))))
= 'e' + ('d' + ('c' + ('b' + "a")))
= 'e' + ('d' + ('c' + "ba"))
= 'e' + ('d' + "cba")
= 'e' + "dcba"
= "edcba"
Each of the first five lines follows from the recursive case of the definition of reverse
; the sixth line follows from the base case; the remaining lines follow from the meaning of concatenation.
Instructions:
Write a StringReverse
program that repeatedly accepts a line of input and produces the reverse form of that line. The program should contain a reverse method that, given a String s
, returns the reverse of s
.
Your program should keep prompting the user for strings and printing out the reverse version until the user enters "Q" or "q", which will signal termination of the program.
Turn in your source code and run outputs.