Objective
To acquire expertise in stack manipulation and management, subroutine linkage and return conventions, and recursive procedures.
Description
You are to create a MIPS programming assignment that returns postfix representation of the input and create an expression tree. Your MIPS program should make use of the expression tree to store the input and provide, by means of an adequate traversal, the value for the expression. Your solution should be structured according to the following steps:
Step 1: Convert expression from infix to postfix. Programming assignment 1 has already solved this step.
Step 2: Create a binary tree (expression tree) from the postfix representation of the input.
Step 3: Compute the value for the expression by means of an adequate tree traversal.
The expressions must be fully parenthesized and include the following operators:
For simplicity all numbers in the expression will have only one base ten digit, (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), in them. Your program must be composed of four states: input, convert-to-postfix, evaluate, and outputstates. You may reuse both input and convert-to-postfix components you have developed for programming assignment 2. At the evaluate state your solution constructs an expression tree and evaluates the expression by means of a tree traversal. At the output state your code must display the complete expression in the postfix notation followed by the = symbol and the expression’s numeric result.
Example
Some valid expressions and their corresponding postfix notations are:
Shown below is the Console display for expression item a) above:
Console
Expression to be evaluated:
((1 - 3) + 5)
13-5+ = 3
Postfix Notation
Consider a set of all valid, completely parenthesized, infix arithmetic expressions consisting of nonnegative integer digits, and the two operations +, -. The following definition gives all such valid expressions:
The character string ((5-1) +3) is an example of a complete parenthesized expression. All valid fully parenthesized infix expressions will have at least one operator.
.data infix: .space 256 postfix: .space 256 stack: .space 256 prompt: .asciiz "Enter String contain infix expression\n(note) Input expression has number must be integer and positive number:" newLine: .asciiz "\n" prompt_postfix: .asciiz "Postfix is: " prompt_result: .asciiz "Result is: " prompt_infix: .asciiz "Infix is: " # get infix .text li $v0, 54 la $a0, prompt la $a1, infix la $a2, 256 syscall la $a0, prompt_infix li $v0, 4 syscall la $a0, infix li $v0, 4 syscall # convert to postfix li $s6, -1 # counter li $s7, -1 # Scounter li $t7, -1 # Pcounter while: la $s1, infix #buffer = $s1 la $t5, postfix #postfix = $t5 la $t6, stack #stack = $t6 li $s2, '+' li $s3, '-' li $s4, '*' li $s5, '/' addi $s6, $s6, 1 # counter ++ # get buffer[counter] add $s1, $s1, $s6 lb $t1, 0($s1) # t1 = value of buffer[counter] beq $t1, $s2, operator # '+' nop beq $t1, $s3, operator # '-' nop beq $t1, $s4, operator # '*' nop beq $t1, $s5, operator # '/' nop beq $t1, 10, n_operator # '\n' nop beq $t1, 32, n_operator # ' ' nop beq $t1, $zero, endWhile nop # push number to postfix addi $t7, $t7, 1 add $t5, $t5, $t7 sb $t1, 0($t5) lb $a0, 1($s1) jal check_number beq $v0, 1, n_operator nop add_space: add $t1, $zero, 32 sb $t1, 1($t5) addi $t7, $t7, 1 j n_operator nop operator: # add to stack ... beq $s7, -1, pushToStack nop add $t6, $t6, $s7 lb $t2, 0($t6) # t2 = value of stack[counter] # check t1 precedence beq $t1, $s2, t1to1 nop beq $t1, $s3, t1to1 nop li $t3, 2 j check_t2 nop t1to1: li $t3, 1 # check t2 precedence check_t2: beq $t2, $s2, t2to1 nop beq $t2, $s3, t2to1 nop li $t4, 2 j compare_precedence nop t2to1: li $t4, 1 compare_precedence: beq $t3, $t4, equal_precedence nop slt $s1, $t3, $t4 beqz $s1, t3_large_t4 nop ################ # t3 < t4 # pop t2 from stack and t2 ==> postfix # get new top stack do again sb $zero, 0($t6) addi $s7, $s7, -1 # scounter ++ addi $t6, $t6, -1 la $t5, postfix #postfix = $t5 addi $t7, $t7, 1 add $t5, $t5, $t7 sb $t2, 0($t5) #addi $s7, $s7, -1 # scounter = scounter - 1 j operator nop ################ t3_large_t4: # push t1 to stack j pushToStack nop ################ equal_precedence: # pop t2 from stack and t2 ==> postfix # push to stack sb $zero, 0($t6) addi $s7, $s7, -1 # scounter ++ addi $t6, $t6, -1 la $t5, postfix #postfix = $t5 addi $t7, $t7, 1 # pcounter ++ add $t5, $t5, $t7 sb $t2, 0($t5) j pushToStack nop ################ pushToStack: la $t6, stack #stack = $t6 addi $s7, $s7, 1 # scounter ++ add $t6, $t6, $s7 sb $t1, 0($t6) n_operator: j while nop ####################### endWhile: addi $s1, $zero, 32 add $t7, $t7, 1 add $t5, $t5, $t7 la $t6, stack add $t6, $t6, $s7 popallstack: lb $t2, 0($t6) # t2 = value of stack[counter] beq $t2, 0, endPostfix sb $zero, 0($t6) addi $s7, $s7, -2 add $t6, $t6, $s7 sb $t2, 0($t5) add $t5, $t5, 1 j popallstack nop endPostfix: ############################################################################### END POSTFIX # print postfix la $a0, prompt_postfix li $v0, 4 syscall la $a0, postfix li $v0, 4 syscall la $a0, newLine li $v0, 4 syscall ############################################################################### Caculate li $s3, 0 # counter la $s2, stack #stack = $s2 # postfix to stack while_p_s: la $s1, postfix #postfix = $s1 add $s1, $s1, $s3 lb $t1, 0($s1) # if null beqz $t1 end_while_p_s nop add $a0, $zero, $t1 jal check_number nop beqz $v0, is_operator nop jal add_number_to_stack nop j continue nop is_operator: jal pop nop add $a1, $zero, $v0 # b jal pop nop add $a0, $zero, $v0 # a add $a2, $zero, $t1 # op jal caculate continue: add $s3, $s3, 1 # counter++ j while_p_s nop #----------------------------------------------------------------- #Procedure caculate # @brief caculate the number ("a op b") # @param[int] a0 : (int) a # @param[int] a1 : (int) b # @param[int] a2 : operator(op) as character #----------------------------------------------------------------- caculate: sw $ra, 0($sp) li $v0, 0 beq $t1, '*', cal_case_mul nop beq $t1, '/', cal_case_div nop beq $t1, '+', cal_case_plus nop beq $t1, '-', cal_case_sub cal_case_mul: mul $v0, $a0, $a1 j cal_push cal_case_div: div $a0, $a1 mflo $v0 j cal_push cal_case_plus: add $v0, $a0, $a1 j cal_push cal_case_sub: sub $v0, $a0, $a1 j cal_push cal_push: add $a0, $v0, $zero jal push nop lw $ra, 0($sp) jr $ra nop #----------------------------------------------------------------- #Procedure add_number_to_stack # @brief get the number and add number to stack at $s2 # @param[in] s3 : counter for postfix string # @param[in] s1 : postfix string # @param[in] t1 : current value #----------------------------------------------------------------- add_number_to_stack: # save $ra sw $ra, 0($sp) li $v0, 0 while_ants: beq $t1, '0', ants_case_0 nop beq $t1, '1', ants_case_1 nop beq $t1, '2', ants_case_2 nop beq $t1, '3', ants_case_3 nop beq $t1, '4', ants_case_4 nop beq $t1, '5', ants_case_5 nop beq $t1, '6', ants_case_6 nop beq $t1, '7', ants_case_7 nop beq $t1, '8', ants_case_8 nop beq $t1, '9', ants_case_9 nop ants_case_0: j ants_end_sw_c ants_case_1: addi $v0, $v0, 1 j ants_end_sw_c nop ants_case_2: addi $v0, $v0, 2 j ants_end_sw_c nop ants_case_3: addi $v0, $v0, 3 j ants_end_sw_c nop ants_case_4: addi $v0, $v0, 4 j ants_end_sw_c nop ants_case_5: addi $v0, $v0, 5 j ants_end_sw_c nop ants_case_6: addi $v0, $v0, 6 j ants_end_sw_c nop ants_case_7: addi $v0, $v0, 7 j ants_end_sw_c nop ants_case_8: addi $v0, $v0, 8 j ants_end_sw_c nop ants_case_9: addi $v0, $v0, 9 j ants_end_sw_c nop ants_end_sw_c: add $s3, $s3, 1 # counter++ la $s1, postfix #postfix = $s1 add $s1, $s1, $s3 lb $t1, 0($s1) beq $t1, $zero, end_while_ants beq $t1, ' ', end_while_ants mul $v0, $v0, 10 j while_ants end_while_ants: add $a0, $zero, $v0 jal push # get $ra lw $ra, 0($sp) jr $ra nop #----------------------------------------------------------------- #Procedure check_number # @brief check character is number or not # @param[int] a0 : character to check # @param[out] v0 : 1 = true; 0 = false #----------------------------------------------------------------- check_number: li $t8, '0' li $t9, '9' beq $t8, $a0, check_number_true beq $t9, $a0, check_number_true slt $v0, $t8, $a0 beqz $v0, check_number_false slt $v0, $a0, $t9 beqz $v0, check_number_false check_number_true: li $v0, 1 jr $ra nop check_number_false: li $v0, 0 jr $ra nop #----------------------------------------------------------------- #Procedure pop # @brief pop from stack at $s2 # @param[out] v0 : value to popped #----------------------------------------------------------------- pop: lw $v0, -4($s2) sw $zero, -4($s2) add $s2, $s2, -4 jr $ra nop #----------------------------------------------------------------- #Procedure push # @brief push to stack at $s2 # @param[in] a0 : value to push #----------------------------------------------------------------- push: sw $a0, 0($s2) add $s2, $s2, 4 jr $ra nop end_while_p_s: # add null to end of stack # print postfix la $a0, prompt_result li $v0, 4 syscall jal pop add $a0, $zero, $v0 li $v0, 1 syscall la $a0, newLine li $v0, 4 syscall
Objective To acquire expertise in stack manipulation and management, subroutine linkage and retur...
This project is designed to practice with OOP, stack data structure, its applications, and C++/Java programming language. You will write a program that reads an infix expression, converts it to a postfix expression, evaluates the postfix expression, and prints out the answer. You must define and implement your own Stack class and a Calculator class. Your Stack class supports standard basic stack operations and you can implement it with an array or a linked list. You should create a class...
In c++ Section 1. Stack ADT – Overview Data Items The data items in a stack are of generic DataType. This means use should use templating and your Node class. Structure The stack data items are linearly ordered from the most recently added (the top) to the least recently added (the bottom). This is a LIFO scheme. Data items are inserted onto (pushed) and removed from (popped) the top of the stack. Operations Constructor. Creates an empty stack. Copy constructor....
Stacks are used by compilers to help in the process of evaluating expressions and generating machine language code.In this exercise, we investigate how compilers evaluate arithmetic expressions consisting only of constants, operators and parentheses. Humans generally write expressions like 3 + 4and 7 / 9in which the operator (+ or / here) is written between its operands—this is called infix notation. Computers “prefer” postfix notation in which the operator is written to the right of its two operands. The preceding...
Total point: 15 Introduction: For this assignment you have to write a c program that will take an infix expression as input and display the postfix expression of the input. After converting the postfix expression, the program should evaluate the expression from the postfix and display the result. What should you submit? Write all the code in a single file and upload the .c file. Problem We as humans write math expression in infix notation, e.g. 5 + 2 (the...
The second programming project involves writing a program that accepts an arithmetic xpression of unsigned integers in postfix notation and builds the arithmetic expression tree that epresents that expression. From that tree, the corresponding fully parenthesized infix expression should be displayed and a file should be generated that contains the three address format instructions. This topic is discussed in the week 4 reading in module 2, section II-B. The main class should create the GUI shown below Three Adddress Generator...
We as humans write math expression in infix notation, e.g. 5 + 2 (the operators are written in-between the operands). In a computer’s language, however, it is preferred to have the operators on the right side of the operands, i.e. 5 2 +. For more complex expressions that include parenthesis and multiple operators, a compiler has to convert the expression into postfix first and then evaluate the resulting postfix. Write a program that takes an “infix” expression as input, uses...
For this project you will implement a simple calculator. Your calculator is going to parse infix algebraic expressions, create the corresponding postfix expressions and then evaluate the postfix expressions. The operators it recognizes are: +, -, * and /. The operands are integers. Your program will either evaluate individual expressions or read from an input file that contains a sequence of infix expressions (one expression per line). When reading from an input file, the output will consist of two files:...
Infix Expression Evaluator For this project, write a C program that will evaluate an infix expression. The algorithm REQUIRED for this program will use two stacks, an operator stack and a value stack. Both stacks MUST be implemented using a linked list. For this program, you are to write functions for the linked list stacks with the following names: int isEmpty (stack); void push (stack, data); data top (stack); void pop (stack); // return TRUE if the stack has no...
Infix Expression Evaluator For this project, write a C program that will evaluate an infix expression. The algorithm REQUIRED for this program will use two stacks, an operator stack and a value stack. Both stacks MUST be implemented using a linked list. For this program, you are to write functions for the linked list stacks with the following names: int isEmpty (stack); void push (stack, data); data top (stack); void pop (stack); // return TRUE if the stack has no...
You will write the following files: mystack.h - contains the class definition for the mystack class. mystack.cpp - contains the definitions for member functions of the mystack class. inpost.cpp - contains your convert() function. inpost.h - contains the function prototype for convert() so that the main() can call it. Each of the files (with the exception of inpost.h) is described in more detail below. All header files should contain header guards to prevent them from being included multiple times in...