Recursion Balanced Parentheses

[kungfu71186]

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

[kungfu71186]

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
         addi  $t5, $s4, 0        # $t5 = addr of current character
mainLoopOrigStart:
         slt   $t6, $t4, $t1      # $t6 = i < count of chars
         beq   $t6, $zero, mainLoopOrigEnd
         lb    $a0, 0($t5)
         addi  $v0, $zero, 11
         syscall
        
         addi  $t4, $t4, 1        # i++
         addi  $t5, $t5, 1        # $t5++, addr of next character
         j     mainLoopOrigStart
 
mainLoopOrigEnd:
         la    $a0, mainString
         addi  $v0, $zero, 4
         syscall

         addi  $a0, $s4, 0        # $a0 = addr of string start
         addi  $a1, $zero, 1      # $a1 = parens level, start at 1
         jal   parens

         # print a blank line
         la    $a0, mainNewline
         addi  $v0, $zero, 4
         syscall
        
         addi  $s0, $s0, 1        # i++
         addi  $s2, $s2, 4        # $s2 = addr of next string
         addi  $s3, $s3, 4        # $s3 = addr of next length
         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
         jr    $ra                # return to 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)
         addi  $v0, $zero, 11
         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
         jr    $ra                # return to 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

        addi   $t1, $zero, 0x28  # '(' Return parens(new address, level++)
        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

        la     $a0, 0($t9)   # Load new address into $a0
        addi   $a1, $a1, 1   # Level++
        jal    parens
		
        lw     $a0, 0($sp)   # Load current first character address
        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:
		
        addi   $t9, $t9, 1
        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
        jr     $ra              # return to caller's code
        

.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
        addi   $v0, $zero, 4
        syscall

        # print level Number
        lw     $a0, 12($sp)
        addi   $v0, $zero, 1
        syscall

        # print newline
        la     $a0, parensPrintNewline
        addi   $v0, $zero, 4
        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
        jr     $ra              # return to caller's code

[bglasser]

I know I'm posting this a little late and you've probably solved your problem or it doesn't matter anymore, but just for shits and giggles I tell you what I Think you problem is... What is happening is that your recursive call counts it's own set of characters, but the caller has no idea what it's count is, so when you back out one level you're losing the character count of the inner level. so in effect you fuction is only counting the characters in its current level and not nested level of parenthesis. What you need to do is to return your count to the caller after each successive call... Hope this helps...