I am now completely lost. I thought i had the correct algorithm to solve this problem, but i can't seem to get it. Anyone have any ideas. I need to balance the parentheses and print each level.

Ex: (this + (is) + an + example)
It will go through it and when it hits a left ( it will call itself again and increment the level.

so it will go up to (this + ( and call itself and kind of start all over until it finds a ). So it gets to (is) and then it exits the loop going through the characters and it prints
(is) from func, level 2
Then when it goes back it will need to start at (this + (is) and continue on like normal until the end so it should print
(this + (is) + an + example) from func, level 1

So overall it would look like
(is) from func, level 2
(this + (is) + an + example) from func, level 1

The problem i am having is when jumping back up to the first level i need to skip over the second level one i just scanned and start up again from after that. I need to keep track of the number of characters ive gone through so far. So in this case it would stop at 8 characters and when i go back to level one i need to start at the 11th character (so 8 (the previous number of chars) + 3 (chars from the recursive call)) and i am not sure how to accomplish this.

Hope thats clear. And by the way i am using MIPs

-Thanks

Edited by kungfu71186: n/a

2
Contributors
2
Replies
8
Views
8 Years
Discussion Span
Last Post by bglasser

Heres the code i have so far. The problem i am having is calculating or saving the number of characters. Everything else seems to work fine if it werent for that. Any ideas? If you run this code you'll see what i mean.

``````# Test with correct ()'s

.data

mainNumFormulas:
.word 1
mainFormulas:
.word mainFormula1
mainLengths:
.word 25

mainFormula1:
#.ascii  "(form)"
.ascii  "(form + (x) + (test) + o)"

mainNewline:
.asciiz "\n"
mainString:
.asciiz " from main\n"

.text
main:
# Function prologue -- even main has one
subu  \$sp, \$sp, 24       # allocate stack space -- default of 24 here
sw    \$fp, 0(\$sp)        # save caller's frame pointer
sw    \$ra, 4(\$sp)        # save return address
addiu \$fp, \$sp, 20       # setup main's frame pointer

# for ( i = 0; i < mainNumFormulas; i++ )
#    find length of string
#    cleanFormula

addi  \$s0, \$zero, 0      # \$s0 = i = 0
la    \$t0, mainNumFormulas
lw    \$s1, 0(\$t0)        # \$s1 = number of strings
la    \$s2, mainFormulas  # \$s2 = addr mainFormulas[0]
la    \$s3, mainLengths   # \$s3 = addr mainLengths[0]
mainLoopBegin:
slt   \$t0, \$s0, \$s1      # \$t0 = i < mainNumFormulas
beq   \$t0, \$zero, mainLoopEnd

lw    \$s4, 0(\$s2)        # \$s4 = addr of start of current string

# loop to print characters of original formula
lw    \$t1, 0(\$s3)        # \$t1 = count of chars in formula
addi  \$t4, \$zero, 0      # i = \$t4 = 0
mainLoopOrigStart:
slt   \$t6, \$t4, \$t1      # \$t6 = i < count of chars
beq   \$t6, \$zero, mainLoopOrigEnd
lb    \$a0, 0(\$t5)
syscall

addi  \$t4, \$t4, 1        # i++
j     mainLoopOrigStart

mainLoopOrigEnd:
la    \$a0, mainString
syscall

addi  \$a1, \$zero, 1      # \$a1 = parens level, start at 1
jal   parens

# print a blank line
la    \$a0, mainNewline
syscall

addi  \$s0, \$s0, 1        # i++
j     mainLoopBegin

mainLoopEnd:

mainDone:
# Epilogue for main -- restore stack & frame pointers and return
lw    \$ra, 4(\$sp)        # get return address from stack
lw    \$fp, 0(\$sp)        # restore frame pointer of caller
addiu \$sp, \$sp, 24       # restore stack pointer of caller

printFormula:
# Function prologue
subu  \$sp, \$sp, 24       # allocate stack space -- default of 24 here
sw    \$fp,  0(\$sp)       # save frame pointer of caller
sw    \$ra,  4(\$sp)       # save return address
sw    \$a0,  8(\$sp)       # save \$a0 = addr of first char to print
sw    \$a1, 12(\$sp)       # save \$a1 = how many chars to print
addiu \$fp, \$sp, 20       # setup frame pointer of printFormula

# for (i = \$a0; i < \$a0 + \$a1; i++)
#    print byte

addi  \$t0, \$a0, 0        # i = \$t0 = start of characters to print
add   \$t1, \$a0, \$a1      # \$t1 = addr of last character to print

printFormulaLoopBegin:
slt   \$t2, \$t0, \$t1      # \$t2 = i < \$a0 + \$a1
beq   \$t2, \$zero, printFormulaLoopEnd

# print the character
lb    \$a0, 0(\$t0)
syscall

addi  \$t0, \$t0, 1        # i++
j     printFormulaLoopBegin

printFormulaLoopEnd:

# Epilogue for printFormula -- restore stack & frame pointers & return
lw    \$a1, 12(\$sp)       # restore \$a1
lw    \$a0,  8(\$sp)       # restore \$a0
lw    \$ra,  4(\$sp)       # get return address from stack
lw    \$fp,  0(\$sp)       # restore frame pointer of caller
addiu \$sp, \$sp, 24       # restore stack pointer of caller

# Your code goes below this line

.text
parens:
# Prologue: set up stack and frame pointers for parens
# Standard 24-byte stack
subu   \$sp, \$sp, 24     # allocate stack space -- default of 24 here
sw     \$fp, 0(\$sp)      # save caller's frame pointer
sw     \$ra, 4(\$sp)      # save return address
sw     \$s0, 8(\$sp)      # save parameter value - Char Counter
sw     \$a0, 12(\$sp)     # save parameter value - Start address
sw     \$a1, 16(\$sp)     # save parameter value - Level
addi   \$fp, \$sp, 24     # setup parens's frame pointer

la     \$t9, 0(\$a0) #Starting address of the string
lb     \$t8, 0(\$t9) #This is the first byte so we can compare it
addi   \$t9, \$t9, 1 #We know first char is already a special char so we start on the next char
li     \$s0, 1      #this will be our counter to specify how many chars to print

parensLoop:
lb     \$t0, 0(\$t9)
addi   \$t1, \$zero, 0x29    # ')'
beq    \$t0, \$t1, parensEnd

addi   \$s0, \$s0, 1 # \$s0 = chars to print

beq    \$v0, -1, parensEpilogue

bne    \$t1, \$t0, parensNextChar

parensRecursiveCall:
subu   \$sp, \$sp, 16  # Grow stack temporarily
sw     \$a0, 0(\$sp)   # Save current first character address
sw     \$s0, 4(\$sp)   # Save current numChars
sw     \$a1, 8(\$sp)   # Save current level

addi   \$a1, \$a1, 1   # Level++
jal    parens

lw     \$s0, 4(\$sp)   # Load current numChars (Add previous numchars before recursive call to this one)
lw     \$a1, 8(\$sp)   # Load current level

lw     \$a0, 0(\$sp)

addiu  \$sp, \$sp, 16 # Restore Stack size

parensNextChar:

j      parensLoop

parensEnd:

#a0 = start address, a1 = level, a2 = chars to print
addi   \$a2, \$s0, 1 # \$a2 = chars to print
jal    parensPrint

parensEpilogue:
# Function epilogue: restore stack & frame pointers and return
lw     \$a1, 16(\$sp)     # restore original value of \$a1 for caller
lw     \$a0, 12(\$sp)     # restore original value of \$a0 for caller
lw     \$s0, 8(\$sp)
lw     \$ra, 4(\$sp)      # get return address from stack
lw     \$fp, 0(\$sp)      # restore the caller's frame pointer
addiu  \$sp, \$sp, 24     # restore the caller's stack pointer

.data
parensPrintNewline: .asciiz "\n"
parensPrintLevel: .asciiz " from parens, level "
.text
parensPrint:
# Prologue: set up stack and frame pointers for parens
# Standard 24-byte stack
subu   \$sp, \$sp, 24     # allocate stack space -- default of 24 here
sw     \$fp, 0(\$sp)      # save caller's frame pointer
sw     \$ra, 4(\$sp)      # save return address
sw     \$a0, 8(\$sp)     # save parameter value - Start address
sw     \$a1, 12(\$sp)     # save parameter value - Level
sw     \$a2, 16(\$sp)     # save parameter value - NumChars
addi   \$fp, \$sp, 24     # setup parens's frame pointer

la     \$a1, 0(\$a2)
jal    printFormula

# print " from parens, level "
la     \$a0, parensPrintLevel
syscall

# print level Number
lw     \$a0, 12(\$sp)
syscall

# print newline
la     \$a0, parensPrintNewline
syscall

parensPrintEnd:
# Function epilogue: restore stack & frame pointers and return
lw     \$a2, 16(\$sp)     # restore original value of \$a2 for caller
lw     \$a1, 12(\$sp)     # restore original value of \$a1 for caller
lw     \$a0, 8(\$sp)     # restore original value of \$a0 for caller
lw     \$ra, 4(\$sp)      # get return address from stack
lw     \$fp, 0(\$sp)      # restore the caller's frame pointer
addiu  \$sp, \$sp, 24     # restore the caller's stack pointer