CS 6301.502. Implementation of advanced data structures and algorithms Fall 2017; Wed, Sep 6. Long Project LP1: Integer arithmetic with arbitrarily large numbers Ver 1.0: Initial description (Wed, Sep 6). Ver 1.1: Changed type of base to long in Num.java Ver 1.2: Added missing line in grammar (level 4) for operator % (Tue, Sep 12) Due: 11:59 PM, Sun, Sep 24 (1st deadline), Sun, Oct 8 (2nd deadline). Max excellence credits: 10.
Code base: Java library: Lists, stacks, queues, sets, maps, hashing, trees. Do not use BigInteger, BigNum, or other libraries that implement arbitrary precision arithmetic.
Starter code and sample drivers are provided. Download lp1-starter.zip here
Your task is to implement the class Num that stores and performs arithmetic operations on arbitrarily large integers. You must use the following data structure for representing Num: Linked list or Array List or Array of long integers, where the digits are in the chosen base. In particular, do not use strings to represent the numbers. Each node of the list stores exactly one long integer. The base is defined to be 10 in the starter code, but you may modify it. In the discussions below, we will use base = 10, using linked lists to represent Num. For base = 10, the number 4628 is represented by the list: 8-->2-->6-->4.
var ; var = postfix expression ; ;When processing the first line above, your program should just output the value of the variable. Other lines will have a postfix expression being assigned to a variable. Your program should evaluate the expression, store it, and print its value to the console. If a line with just a semicolon is encountered, then your program should stop processing, and ignore any additional lines in the input. At the end, output the internal representation of the last variable that was assigned a value. Here is a sample input and its output:
Sample input: a = 999 ; b = 8 ; c = a b ^ ; d = a b + ; ; Its output: 999 8 992027944069944027992001 1007 10: 7 0 0 1
Implement the Shunting Yard algorithm: https://en.wikipedia.org/wiki/Shunting-yard_algorithm to be able to parse arithmetic expressions using the following precedence rules (highest to the lowest).
lineno var = expression ; # infix expression lineno var ? NZ ; # continue execution from lineno NZ if var != 0 lineno var ? NZ : ZR ; # continue execution from lineno NZ if var != 0, # and from line ZR if var == 0where expression is a valid arithmetic expression formed by identifiers (variables) and numbers. Nothing should be output when Level 4 input lines are processed. The following grammar generates valid expressions. Note that there is no unary minus operator. Tokens are separated by spaces, so that input can be parsed easily. See Tokenizer.java for an example.
expression:: expression + term | expression - term | term term:: term * factor | term / factor | term % factor | factor factor:: uterm ^ factor | uterm uterm:: uterm | | atom atom:: var | number | ( expression ) var:: [a-z] number:: 0 | [1-9][0-9]*
Execution starts from the first line, and proceeds line by line. Lines of the form "lineno var ? NZ ;" and "lineno var ? NZ : ZR ;" change the execution sequence, depending on whether the var is equal to 0 or not. If x = 5, then upon executing the line "10 x ? 8", your program should continue from line with lineno=8. On the other hand, if x = 0, then the line "10 x ? 8" has no effect, and execution continues sequentially. Upon executing the last line, the program comes to a stop.
Assume that the input does not have multiple lines with the same lineno. Line numbers do not have to be sequential or in ascending order. Inputs will not try to access the value of a var that has not yet been assigned a value.
Sample input for level 4, with explanations: x = 10 ; # Level 3: postfix expression that assigns 10 to x p = 1 ; # Level 3: p is assigned 1 8 p = p * x ; # Level 4: expression in infix notation, lineno=8 10 x = x - 1 ; # Level 4: x is decremented by 1 15 x ? 8 ; # Level 4: continue from line with lineno=8 if x != 0 p ; # Level 3: print the value of p ; The above input calculates 10! by looping between lines with lineno=8 and lineno=15, until x becomes zero. Its output is: 10 # Output from "x = 10 ;" 1 # Output from "x = 10 ;" 3628800 # Output from "p ;" 10: 0 0 8 8 2 6 3 # The last line executed was "p ;", so printList() of var p