Xây dựng chương trình MIPS sau (không bắt buộc dùng thủ tục/hàm):
Nhập vào chuỗi biểu thức gồm có các toán tử sau: + – * / (_), và tính kết quả của biểu thức đó.
Nhập vào chuỗi biểu thức gồm có các toán tử sau: + – * / (_), và tính kết quả của biểu thức đó.
Ví dụ: 12*3+24/(9-3)-90
Ghi chú:
+ Độ ưu tiên của toán tử: 1: (_) ; 2: * / ; 3: + -
+ Các toán hạng là số nguyên được giới hạn trong đoạn [0,999]
+ Tìm hiểu stack và thuật toán balan ngược (trong cấu trúc dữ liệu)
+ Kết quả của biểu thức: số nguyên hoặc số thực (chỉ cần chọn 1 trong 2) hoặc số thực (chỉ cần chọn 1 trong 2)
Ghi chú:
+ Độ ưu tiên của toán tử: 1: (_) ; 2: * / ; 3: + -
+ Các toán hạng là số nguyên được giới hạn trong đoạn [0,999]
+ Tìm hiểu stack và thuật toán balan ngược (trong cấu trúc dữ liệu)
+ Kết quả của biểu thức: số nguyên hoặc số thực (chỉ cần chọn 1 trong 2) hoặc số thực (chỉ cần chọn 1 trong 2)
Đây là bài làm của tôi:
# $s1: expression string
# $sp, $t0: stack
# $s0, $t1: queue
.data
text_1: .asciiz "Nhap bieu thuc: "
text_2: .asciiz "Gia tri bieu thuc: "
text_3: .asciiz "Bieu thuc khong dung!"
.text
main:
move $t0, $sp
addi $s0, $sp, -102400
move $t1, $s0
addi $s1, $s0, -102400
li $v0, 4 #print string
la $a0, text_1
syscall
addi $s1, $s1, -1024
move $a0, $s1
li $v0, 8 #read string
li $a1, 1024
syscall
Infix2Postfix:
lbu $t2, 0($s1)
beq $t2, 10, end_Infix2Postfix # if s[0]=='n' goto end_Infix2Postfix
beq $t2, '(',open
beq $t2, ')',close
beq $t2, '+',operator
beq $t2, '-',operator
beq $t2, '*',operator
beq $t2, '/',operator
move $a0, $t2
jal Is_number
beq $v0, 1, operand
addi $s1, $s1, 1 # next character
j Infix2Postfix
open:
li $a0, 0
li $a1, 0
jal Push_stack
addi $s1, $s1, 1 # next character
j Infix2Postfix
close:
jal Is_Empty_stack
beq $v0, 1, Expression_Error
jal Pop_stack
beq $v0, $zero, end_close
move $a0, $v0
move $a1, $v1
jal Push_queue
j close
end_close:
addi $s1, $s1, 1 # next character
j Infix2Postfix
operator:
beq $t2, '+',o1
beq $t2, '-',o1
beq $t2, '*',o2
beq $t2, '/',o2
o1:
li $t3, 1
j while_o
o2:
li $t3, 2
while_o:
jal Is_Empty_stack
beq $v0, 1, end_while_o
jal Top_stack
slt $t4, $v0, $t3
beq $t4, 1, end_while_o
jal Pop_stack
move $a0, $v0
move $a1, $v1
jal Push_queue
end_while_o:
move $a0, $t3
move $a1, $t2
jal Push_stack
addi $s1, $s1, 1 # next character
j Infix2Postfix
operand:
sub $t3, $t2, '0'
while_number:
lbu $t2, 1($s1)
move $a0, $t2
jal Is_number
beq $v0, 0, end_while_number
mul $t3, $t3, 10
sub $t2, $t2, '0'
add $t3, $t3, $t2
addi $s1, $s1, 1
j while_number
end_while_number:
li $a0, 3
move $a1, $t3
jal Push_queue
addi $s1, $s1, 1 # next character
j Infix2Postfix
end_Infix2Postfix:
while_not_Empty_stack:
jal Is_Empty_stack
beq $v0, 1, end_while_not_Empty_stack
jal Pop_stack
move $a0, $v0
move $a1, $v1
jal Push_queue
j while_not_Empty_stack
end_while_not_Empty_stack:
while_not_Empty_queue:
jal Is_Empty_queue
beq $v0, 1, end_while_not_Empty_queue
jal Pop_queue
beq $v0, 3, _operand
move $a2, $v1
jal Pop_stack
bne $v0, 3, Expression_Error
move $a1, $v1
jal Pop_stack
bne $v0, 3, Expression_Error
move $a0, $v1
jal calculate
li $a0, 3
move $a1, $v0
jal Push_stack
j while_not_Empty_queue
_operand:
move $a0, $v0
move $a1, $v1
jal Push_stack
j while_not_Empty_queue
end_while_not_Empty_queue:
li $v0, 4 #print string
la $a0, text_2
syscall
jal Pop_stack
move $a0, $v1
li $v0, 1
syscall
end_program:
li $v0, 10 #exit
syscall
Expression_Error:
li $v0, 4 #print string
la $a0, text_3
syscall
j end_program
Is_number:
beq $a0, '0',_number
beq $a0, '1',_number
beq $a0, '2',_number
beq $a0, '3',_number
beq $a0, '4',_number
beq $a0, '5',_number
beq $a0, '6',_number
beq $a0, '7',_number
beq $a0, '8',_number
beq $a0, '9',_number
li $v0, 0
jr $ra
_number:
li $v0, 1
jr $ra
calculate:
beq $a2, '+', _add
beq $a2, '-', _sub
beq $a2, '*', _mul
div $a0, $a1
mflo $v0
jr $ra
_add:
add $v0, $a0, $a1
jr $ra
_sub:
sub $v0, $a0, $a1
jr $ra
_mul:
mul $v0, $a0, $a1
jr $ra
Push_stack:
addi $t0, $t0, -8
sw $a0, 0($t0) #save type of token
sw $a1, 4($t0) #save value of token
jr $ra
Push_queue:
addi $s0, $s0, -8
sw $a0, 0($s0) #save type of token
sw $a1, 4($s0) #save value of token
jr $ra
Pop_stack:
lw $v0, 0($t0)
lw $v1, 4($t0)
addi $t0, $t0, 8
jr $ra
Top_stack:
lw $v0, 0($t0)
lw $v1, 4($t0)
jr $ra
Pop_queue:
lw $v0, -8($t1)
lw $v1, -4($t1)
addi $t1, $t1, -8
jr $ra
Is_Empty_stack:
beq $sp, $t0, Empty_stack
li $v0, 0
jr $ra
Empty_stack:
li $v0, 1
jr $ra
Is_Empty_queue:
beq $s0, $t1, Empty_queue
li $v0, 0
jr $ra
Empty_queue:
li $v0, 1
jr $ra
# $sp, $t0: stack
# $s0, $t1: queue
.data
text_1: .asciiz "Nhap bieu thuc: "
text_2: .asciiz "Gia tri bieu thuc: "
text_3: .asciiz "Bieu thuc khong dung!"
.text
main:
move $t0, $sp
addi $s0, $sp, -102400
move $t1, $s0
addi $s1, $s0, -102400
li $v0, 4 #print string
la $a0, text_1
syscall
addi $s1, $s1, -1024
move $a0, $s1
li $v0, 8 #read string
li $a1, 1024
syscall
Infix2Postfix:
lbu $t2, 0($s1)
beq $t2, 10, end_Infix2Postfix # if s[0]=='n' goto end_Infix2Postfix
beq $t2, '(',open
beq $t2, ')',close
beq $t2, '+',operator
beq $t2, '-',operator
beq $t2, '*',operator
beq $t2, '/',operator
move $a0, $t2
jal Is_number
beq $v0, 1, operand
addi $s1, $s1, 1 # next character
j Infix2Postfix
open:
li $a0, 0
li $a1, 0
jal Push_stack
addi $s1, $s1, 1 # next character
j Infix2Postfix
close:
jal Is_Empty_stack
beq $v0, 1, Expression_Error
jal Pop_stack
beq $v0, $zero, end_close
move $a0, $v0
move $a1, $v1
jal Push_queue
j close
end_close:
addi $s1, $s1, 1 # next character
j Infix2Postfix
operator:
beq $t2, '+',o1
beq $t2, '-',o1
beq $t2, '*',o2
beq $t2, '/',o2
o1:
li $t3, 1
j while_o
o2:
li $t3, 2
while_o:
jal Is_Empty_stack
beq $v0, 1, end_while_o
jal Top_stack
slt $t4, $v0, $t3
beq $t4, 1, end_while_o
jal Pop_stack
move $a0, $v0
move $a1, $v1
jal Push_queue
end_while_o:
move $a0, $t3
move $a1, $t2
jal Push_stack
addi $s1, $s1, 1 # next character
j Infix2Postfix
operand:
sub $t3, $t2, '0'
while_number:
lbu $t2, 1($s1)
move $a0, $t2
jal Is_number
beq $v0, 0, end_while_number
mul $t3, $t3, 10
sub $t2, $t2, '0'
add $t3, $t3, $t2
addi $s1, $s1, 1
j while_number
end_while_number:
li $a0, 3
move $a1, $t3
jal Push_queue
addi $s1, $s1, 1 # next character
j Infix2Postfix
end_Infix2Postfix:
while_not_Empty_stack:
jal Is_Empty_stack
beq $v0, 1, end_while_not_Empty_stack
jal Pop_stack
move $a0, $v0
move $a1, $v1
jal Push_queue
j while_not_Empty_stack
end_while_not_Empty_stack:
while_not_Empty_queue:
jal Is_Empty_queue
beq $v0, 1, end_while_not_Empty_queue
jal Pop_queue
beq $v0, 3, _operand
move $a2, $v1
jal Pop_stack
bne $v0, 3, Expression_Error
move $a1, $v1
jal Pop_stack
bne $v0, 3, Expression_Error
move $a0, $v1
jal calculate
li $a0, 3
move $a1, $v0
jal Push_stack
j while_not_Empty_queue
_operand:
move $a0, $v0
move $a1, $v1
jal Push_stack
j while_not_Empty_queue
end_while_not_Empty_queue:
li $v0, 4 #print string
la $a0, text_2
syscall
jal Pop_stack
move $a0, $v1
li $v0, 1
syscall
end_program:
li $v0, 10 #exit
syscall
Expression_Error:
li $v0, 4 #print string
la $a0, text_3
syscall
j end_program
Is_number:
beq $a0, '0',_number
beq $a0, '1',_number
beq $a0, '2',_number
beq $a0, '3',_number
beq $a0, '4',_number
beq $a0, '5',_number
beq $a0, '6',_number
beq $a0, '7',_number
beq $a0, '8',_number
beq $a0, '9',_number
li $v0, 0
jr $ra
_number:
li $v0, 1
jr $ra
calculate:
beq $a2, '+', _add
beq $a2, '-', _sub
beq $a2, '*', _mul
div $a0, $a1
mflo $v0
jr $ra
_add:
add $v0, $a0, $a1
jr $ra
_sub:
sub $v0, $a0, $a1
jr $ra
_mul:
mul $v0, $a0, $a1
jr $ra
Push_stack:
addi $t0, $t0, -8
sw $a0, 0($t0) #save type of token
sw $a1, 4($t0) #save value of token
jr $ra
Push_queue:
addi $s0, $s0, -8
sw $a0, 0($s0) #save type of token
sw $a1, 4($s0) #save value of token
jr $ra
Pop_stack:
lw $v0, 0($t0)
lw $v1, 4($t0)
addi $t0, $t0, 8
jr $ra
Top_stack:
lw $v0, 0($t0)
lw $v1, 4($t0)
jr $ra
Pop_queue:
lw $v0, -8($t1)
lw $v1, -4($t1)
addi $t1, $t1, -8
jr $ra
Is_Empty_stack:
beq $sp, $t0, Empty_stack
li $v0, 0
jr $ra
Empty_stack:
li $v0, 1
jr $ra
Is_Empty_queue:
beq $s0, $t1, Empty_queue
li $v0, 0
jr $ra
Empty_queue:
li $v0, 1
jr $ra
0 nhận xét