.data
    newline:   .asciiz "\n"
    msg_eval:   .asciiz "Expression to be evaluated:\n"
    msg_eq:   .asciiz "="
    #inbuf:   .asciiz "1+3-5"
    #inbuf:   .asciiz "((1 - 3) + 5)"
    inbuf:   .asciiz "1+2+4-5-7+3-6"
    #inbuf:   .space 128
    outbuf:   .space 128
        .text
.globl main

main:
    li $v0, 4 # print_str
    la $a0, msg_eval # "Expression to be evaluated:\n"
    syscall

    # Input
    li $v0, 8 # read_string
    la $a0, inbuf
    li $a1, 128
    #syscall

    # debug
    li $v0, 4 # print_str
    la $a0, inbuf
    syscall
    li $v0, 4 # print_str
    la $a0, newline
    syscall

    # Convert to Postfix
    move $s0, $sp # s0 = stackStart
    la $t0, inbuf # t0 = current char
    la $t4, outbuf # t4 = current out char
    inLoop:
        lbu $t2, ($t0) # t2 = char[t0]
        beq $t2, 0, stack_loop1 # t2 == '\0'

        beq $t2, 32, inLoop_continue # skip ' '
        beq $t2, 10, inLoop_continue # skip '\n'
        beq $t2, 43, inLoop_pm # +
        beq $t2, 45, inLoop_pm # -
        beq $t2, 40, inLoop_op # (
        beq $t2, 41, inLoop_cp # )

        # default (is a #)
        sb $t2, ($t4) # output += char
        addu $t4, $t4, 1

        j inLoop_continue

        inLoop_pm: # + | -
            li $a1, 1 # push = true
            jal stack_loop

            subu $sp, $sp, 1
            sb $t2, ($sp) # stack push t2

            j inLoop_continue
        inLoop_op: # (
            subu $sp, $sp, 1
            sb $t2, ($sp) # stack push t2

            j inLoop_continue
        inLoop_cp: # )
            li $a1, 0 # push = false
            jal stack_loop

            j inLoop_continue
        inLoop_continue:
            addu $t0, $t0, 1 # t0++
            j inLoop
    stack_loop1:
        beq $sp, $s0, stack_loop1_end # while stack !empty

        lb   $t3, ($sp) # stack pop t3
        addu $sp, $sp, 1

        sb $t3, ($t4) # output += char
        addu $t4, $t4, 1

        j stack_loop1
    stack_loop1_end:

    li $t5, 0
    sb $t5, ($t4) # Null terminate string '\0'


    # Postfix to Tree
    la $t0, outbuf
    loop_postfix:
        lbu $t2, ($t0) # t2 = char[t0]
        beq $t2, 0, loop_postfix_end # t2 == '\0'

        beq $t2, 43, loop_postfix_pm # +
        beq $t2, 45, loop_postfix_pm # -

        # default (is a #)
        andi $t2, $t2, 0x0F # convert char to int

        li $a0, 12 # bytes
        li $v0, 9 # node* = malloc
        syscall
        sw $t2, 0($v0) # val = #
        sw $zero, 4($v0) # a* = 0
        sw $zero, 8($v0) # b* = 0

        subu $sp, $sp, 4
        sw $v0, ($sp) # stack push t2

        j loop_postfix_continue

        loop_postfix_pm: # + | -
            lw $t5, ($sp) # b* = stack pop
            addu $sp, $sp, 4

            lw $t6, ($sp) # a* = stack pop
            addu $sp, $sp, 4

            li $a0, 12 # bytes
            li $v0, 9 # node* = malloc
            syscall

            # init node
            sb $t2, 0($v0)# val = op
            sw $t6, 4($v0)# a*
            sw $t5, 8($v0)# b*

            subu $sp, $sp, 4
            sw $v0, ($sp) # stack push node*
        loop_postfix_continue:
            addu $t0, $t0, 1 # t0++
            j loop_postfix
    loop_postfix_end:

    # Evaluate Tree
    lw $a1, ($sp) # a1 = head node* !!!!!!!!!!
    jal solve_tree

    # Output Postfix Expression
    li $v0, 4 # print_str
    la $a0, outbuf
    syscall

    li $v0, 4 # print_str
    la $a0, msg_eq
    syscall

    li $v0, 1 # print_int
    move   $a0, $a2 # returned value
    syscall

    li $v0, 10 # exit
    syscall

stack_loop: # a1 = push
    beq $sp, $s0, stack_loop_end # while stack !empty

    lb   $t3, ($sp) # stack pop t3
    addu $sp, $sp, 1

    bne $t3, 40, stack_loop_else # char != (
    beq $a1, 0, stack_loop_end # break

    subu $sp, $sp, 1
    sb $t3, ($sp) # stack push t3

    j stack_loop_end # break

    stack_loop_else:
        sb $t3, ($t4) # output += char
        addu $t4, $t4, 1

        j stack_loop
    stack_loop_end:
        jr $ra

solve_tree: # a1 = node*
    lw $t0, 0($a1) # t0 = value
    lw $t1, 4($a1) # t1 = a
    #lw $t2, 8($a1) # t2 = b

    bne $t1, $zero, solve_tree_nested # t1 != 0

    move $a2, $t0 # return #
    jr $ra

    solve_tree_nested: # t0 == op
        sw   $a1, -4($sp) # stack push node*
        sw   $ra, -8($sp) # stack push ra
        subu $sp, $sp, 8

        move $a1, $t1 # a1 = a
        jal solve_tree # a
        lw $ra, ($sp) # stack pop ra
        subu $sp, $sp, 4
        sw   $a2, ($sp) # stack push a

        lw $a1, 8($sp) # a1 = node*
        lw $a1, 8($a1) # a1 = b
        subu $sp, $sp, 4
        sw $ra, ($sp) # stack push ra
        jal solve_tree # b
        lw $ra, ($sp) # stack pop ra
        subu $sp, $sp, 4
        sw   $a2, ($sp) # stack push b

        lw   $a1, 16($sp) # stack peek node* ????????????
        lw $t0, 0($a1) # t0 = op
        lw $t1, ($sp) # t1 = pop b
        lw $t2, 8($sp) # t2 = pop a
        addu $sp, $sp, 12

        lw $ra, ($sp)
        addu $sp, $sp, 8

        bne $t0, 43, solve_tree_nested_minus # op != +
        add $a2, $t2, $t1 # return a + b ????????????
        jr $ra

        solve_tree_nested_minus:
        sub $a2, $t2, $t1 # return a - b
        jr $ra