Mips Assembly - Strings

Question

I started learning some Mips Assembly development and I encountered in the following question, which I found hard to solve:

A string which is recieved from the user consists only from Brackets, left and right. 
A legal string is one that for each left bracket has a closing right bracket.
A bracket can be inside another bracket, as long as it has a closing bracket.

The following "strings" are legal:
(), (()), ((()))

The following "strings" are not legal:
())), (, ((((()

An empty string is also legal.

It is very clear to me that the number of right and left brackets has to be equal.

If I had to do it in Java, I would start "counting" the left brackets, until I reach a right bracket, and then check if the numbers match.

However, I don't know how to it on Mips.

EDIT: see answer below.

Just write it in java, then translate each line into one or more MIPS instructions. — markgz, Sep 25 '14 at 18:30
The algorithm would likely be the same. What specifically are you having trouble with? If you don't know any MIPS assembly at all you should start by reading a book or tutorial on the subject. — Michael, Sep 25 '14 at 18:30
I think the term is "well-atched parentheses" and you can read [this question and its answer](http://stackoverflow.com/questions/2509358/how-to-find-validity-of-a-string-of-parentheses-curly-brackets-and-square-brack) for details and applications. — Niklas Rosencrantz, Sep 26 '14 at 00:27

score 1 · Answer 1 · answered Sep 25 '14 at 18:54

I think I got the answer right, with a little help from the guys here. The key point is to know that if at any point, there are more right than left brackets - exit.

    .data
theArray:   .space 64
str: .asciiz "\n enter a string, consists only of brackets. enter 0 in the end. \n"
msg1: "\n legal string\n"
msg2: "\n the string is not legal"

.text
    li $t0, 0 #left bracket counter
    li $t1, 0 #right bracket counter
    la $s0, theArray #pointer the string

loop:
    la $a0, str
    li $v0, 4
    syscall
    li $v0, 12
    syscall 

    beq $v0, 48, checkLegal
    beq $v0, 40, leftBracket
    beq $v0, 41, rightBracket
    j exit
leftBracket:
    addi $t0, $t0, 1
    j loop

rightBracket:
    addi $t1, $t1, 1
    #if at any point there are more right brackets than left, the string is not legal
    bgt $t1, $t0, notLegal
    j loop      

checkLegal:
    beq $t1, $t0, printLegal
    j notLegal
printLegal:
    la $a0, msg1
    li $v0, 4
    syscall
    j exit 
notLegal:
    la $a0, msg2
    li $v0, 4
    syscall

exit:
    li $v0, 10
    syscall

Mips Assembly - Strings

1 Answers1