 |
Rekursion och strängar |
|
Rekursion och strängar |
Uppgiften syftar till att ge kunskap och förståelse för hur:
Senast uppdaterat: Tue Nov 29 16:34:56 CET 2005
~ karl
I uppgift ett lärde vi oss hantera ord och arrayer av ord tolkade som heltal. Nu skall vi bekanta oss med en annan typ av arrayer, nämligen arrayer av bytes. För att koda bokstäver representeras varje bokstav av ett specifikt tal. En array av sådana tal kan alltså användas för att koda en sträng av bokstäver.
Det vanligaste sättet att koda bokstäver är ASCII. Med en sträng menas vanligen en adress till en array av bytes där varje byte tolkas som en bokstav enligt ASCII-kodningen. För att veta när en sträng är slut avslutas den med det speciella tecknet NULL.
För människor är det oftast enkelt att skilja på olika typer av strängar. Genom att tolka innebörden av en sträng kan vi dela in strängar i olika klasser.
Exempel: strängen "123" kan tolkas som ett possitivt heltal medans strängen "AbBa" inte kan tolkas som ett heltal.
Ett palindrom (av grekiskans palindromos = tillbakalöpande) är en text som blir likadan om man läser den baklänges. Detta förutsätter att man ignorerar mellanslag, punkter och andra skiljetecken samt inte gör skillnad på liten och stor bokstav.
Exempel: strängen "123" är inte ett palindrom men strängen "AbBa" är ett palindrom.
Exempel: strängen "Dromedaren Alpotto planerade mord" är ett palindrom (men inte ett heltal).
Vid anrop till subrutiner sparas returadressen i det speciella registret $ra. I bland är det praktiskt att låta en subrutin anropa andra subrutiner och då måste returvärdet i $ra sparas undan innan nästa subrutinanrop. Ett bra ställa att spara undan detta värde är stacken. Ett specialfall av detta är när en subrutin anropar sig själv, sk rekursion.
Exempel: om vi vill beräkna 5! så vet vi att detta betyder 5! = 1*2*3*4*5 = 120. I pseudokod kan vi definiera definiera en funktion som beräknar n! enligt:
fakultet(n) {
if (n==0)
return 1;
else
return n*fakultet(n-1);
}
I exemplet ovan ser vi att argumentet till det rekursiva anropet minskar för varje rekursivt steg för att till slut anta värdet n==0 vilket utgör vårt basfall.
Ni skall skriva en subrutin strLength_r som beräknar längden av en null-terminerad sträng mha rekursion. Notera att det finns en given subrutin strLength som beräknar längden på en sträng mha itteration (loop). Tänk ut ett lämpligt basfall och rekursivt steg och skriv sedan en rekursiv version.
Ni skall skriva en subrutin strIsInt som kontrollerar om en sträng kan tolkas som ett possitivt heltal eller ej. Ni får själva välja om ni vill skriva en rekursiv lösning eller en iterativ.
Ni skall skriva en rekursiv subrutin strIsPallindrome_r som kontrollerar om en sträng kan tolkas som ett pallindrom. Ni behöver ej hantera mellanslag eller andra skiljetecken, dock skall det inte spela någon roll om små eller stora bokstäver används.
Observera att all kod ni skriver skall vara försedd med lämpliga kommentarer. Vad som menas med lämpliga kommentarer kommer att framgå under genomgången. För inspiration och vägledning för hur bra kommentarer kan se ut, titta tex på på kommentarerna i strLength.
Ni skall bygga vidare på koden nedan:
##############################################################################
##
## DESCRIPTION: Computer Systems 1 - part 1 (DARK)
##
## Assignment 2: Strings and recursion.
##
## Add a short descriptive summary...
##
##
## AUTHOR(S): Student One <student.one@student.uu.se>
## Student Two <student.two@student.uu.se>
##
## HISTORY: November XX, 2004. First version.
##
## November ZZ, 2004. Fixed infinite recurision bug.
##
##############################################################################
##############################################################################
## Data Segment
##############################################################################
.data
MSG1: .asciiz "\nMata in en sträng: "
MSG2: .asciiz "\nDu matade in: "
MSG3: .asciiz "\nSträngens längd (itteration): "
MSG3b: .asciiz "\nSträngens längd (reursion): "
MSG4: .asciiz "\nSträngen är ett palindrom\n"
MSG5: .asciiz "\nSträngen är inte palindrom\n"
MSG6: .asciiz "\nSträngen är ett heltal\n"
MSG7: .asciiz "\nSträngen är inte ett heltal\n"
NL: .asciiz "\n"
BUFF: .space 80 # a 80 character string buffer
##############################################################################
## Text Segment
##############################################################################
.text
.globl main
#-----------------------------------------------------------------------------
# Main Start
#-----------------------------------------------------------------------------
main: addi $sp, $sp, -4 # Push return adress
sw $ra, 0($sp)
# "Mata in en stäng:"
li $v0, 4 # system call for print_str
la $a0, MSG1 # address of string to print
syscall # print the string
# read string from user into buffert
li $v0, 8 # system call for read_str
la $a0, BUFF # address to buffer
li $a1, 80 # length of buffer, will read max 79
# characters and terminate with null
syscall
# "du matade in:"
li $v0, 4 # system call for print_str
la $a0, MSG2 # address of string to print
syscall # print the string
la $a0, BUFF # address of string to print
syscall # print the string
# "Strängens längd är (iteration):"
li $v0, 4 # system call for print_str
la $a0, MSG3 # address of string to print
syscall # print the string
# Call strLength procedure to get length of string.
la $a0, BUFF
jal strLength # call strLength
move $s0, $v0 # save the result for future use
# Print the length.
li $v0, 1 # system call code for print_int
move $a0, $s0 # integer to print ($a0)
syscall # print the integer
li $v0, 4 # system call for print_str
la $a0, NL # print a new-line
syscall
# "Strängens längd är (rekursion):"
li $v0, 4 # system call for print_str
la $a0, MSG3b # address of string to print
syscall # print the string
# Call strLength procedure to get length of string.
la $a0, BUFF
jal strLength_r # call strLength
move $s0, $v0 # save the result for future use
# Print the length.
li $v0, 1 # system call code for print_int
move $a0, $s0 # integer to print ($a0)
syscall # print the integer
li $v0, 4 # system call for print_str
la $a0, NL # print a new-line
syscall
# Call strIsInt to check if string is an integer.
la $a0, BUFF
add $a1, $s0, $zero
jal strIsInt
# Check result and print report.
beq $v0, $zero, notInteger
# "Strängen är ett heltal"
li $v0, 4 # system call for print_str
la $a0, MSG6 # address of string to print
syscall # print the string
j testPalindrome
notInteger:
# "Strängen är inte ett heltal"
li $v0, 4 # system call for print_str
la $a0, MSG7 # address of string to print
syscall # print the string
testPalindrome:
# Call strIsPalindrome_r to check if string is a palindrome.
la $a0, BUFF
add $a1, $s0, $zero
jal strIsPalindrome_r
# Check result and print report.
beq $v0, $zero, notPalindrome
# "Strängens är ett palindrom"
li $v0, 4 # system call for print_str
la $a0, MSG4 # address of string to print
syscall # print the string
j theEnd
notPalindrome:
# "Strängens är inte ett palindrom"
li $v0, 4 # system call for print_str
la $a0, MSG5 # address of string to print
syscall # print the string
theEnd:
# j main # uncomment if you want the program to loop forever.
lw $ra, 0($sp) # pop return adress and return to caller (exit)
addiu $sp, $sp, 4
jr $ra
#-----------------------------------------------------------------------------
# Main End
#-----------------------------------------------------------------------------
#------------------------------------------------------------------------------
# INPUT: $a0 - Pointer (address to first character) to string.
#
# OUTPUT: $v0 - length of string in bytes, terminating null character
# is not counted.
#------------------------------------------------------------------------------
strLength:
add $v0, $zero, $zero # initialize length to zero
addi $t1, $zero, 0x20 # ASCII(space)=0x20
while: lb $t0, 0($a0) # look at each character (byte) in $t0
# searh for ending '\n' (ascii 0).
blt $t0, $t1, done # Trick! Will stop count as soon
# a non-printable character is
# encountered.
addi $a0, $a0, 1 # next character
addi $v0, $v0, 1 # increment counter
j while
done: sub $a0, $a0, $v0 # restore input string pointer
jr $ra # return to caller
#------------------------------------------------------------------------------
# INPUT: $a0 - Pointer (address to first character) to string.
#
# OUTPUT: $v0 - length of string in bytes, terminating null character
# is not counted.
#------------------------------------------------------------------------------
strLength_r:
addi $sp, $sp, -4 # Must push return address since we use
sw $ra, 0($sp) # a recursive procedure call later.
add $v0, $zero, $zero # initialize result to zero
##############################
#### WRITE YOUR CODE HERE ####
##############################
lw $ra, 0($sp) # pop return address
addi $sp, $sp, 4
jr $ra # return to caller
#------------------------------------------------------------------------------
# INPUT: $a0 - Pointer to string
# $a1 - Length of string (trailing null excluded)
#
# OUTPUT: $v0 - 1 string is integer
# - 0 string is not integer
#------------------------------------------------------------------------------
strIsInt:
add $v0, $zero, $zero # initialize result to zero
##############################
#### WRITE YOUR CODE HERE ####
##############################
jr $ra # return to caller
#------------------------------------------------------------------------------
# INPUT: $a0 - Pointer to string
# $a1 - Length of string (trailing null excluded)
#
# OUTPUT: $v0 - 1 string is a palindrome
# - 0 string is not a palindrome
#
# NOTE: Although more efficient solutions exists, a recursive
# is used as an exercise.
#------------------------------------------------------------------------------
strIsPalindrome_r:
addi $sp, $sp, -4 # Must push return address since we use
sw $ra, 0($sp) # a recursive procedure call later.
##############################
#### WRITE YOUR CODE HERE ####
##############################
# You shold include the comments below, use them to structure
# your solution.
# The empty string is always a palindrome.
# A one-character string is always a palindrome.
# Are the first and last character equal?
# Palindrome check is case-insensitive, e.g., "AbBa"is a palindrome.
# If two characters only differs in case, the absolute value of the
# difference bewteen the ASCII-values is exactly 0x20.
# If first and last character are equal, if the string in
# between is a palindrome the whole string is a palindrome.
# Use a recursive procedure call to check this.
lw $ra, 0($sp) # pop return address
addi $sp, $sp, 4
jr $ra # return to caller
Innan ni lämnar in, visst har ni kollat att allt funkar för några "specialfall":
| "" | Tom sträng! Är en tom sträng ett palindrom? Är en tom sträng ett heltal? |
| "123/4:9" | Randvärden, '/' och ':' ligger på gränsen till siffer-tecknen i ASCII-tabellen. |
| "aBC99cbA" | Kolla att stora och små boksäver inte spelar någon roll. |
| "67544576" | Ett heltal som är ett palindrom. |