Description

2          Assignment

 

You have to implement an interpreter that recognizes assignments  and performs calculations, evaluating an arbitrary expression that accepts

• Rational numbers (e.g., 5669 or -3.5);
• Parentheses ‘(‘ and ‘)’;
• Operators “+”, “-“, “*”, “/”, and “^”. The latter operator is that of exponentiation, which, has the highest precedence. Your code must handle all rational exponents—including the negative ones.^[1]
• The assignments of the form ‘define x = <expression>’, where x is an identifier. (All identifiers must be stored in a hash table so that they can be searched effectively.)

 

 

 

Your program must use a recursive-descent technique, as explained in class, based on the following production rules:

 

 

<calculation> → <expression> |^[2] “define” <identifier> “=” <expression>

<identifier> → <alphanumericstring>

<alphanumericstring> → [<alphastring>{<digitstring>}^[3] ] ^[4]

<alphastring> → [<letter>]

<letter> → ‘a’|…|‘z’| ‘A’|…|‘Z’ 

<digitstring> → [<digit>]

<digit> → ‘0’|’1’|’2’|’3’|’4’|’5’|’6’|’7’|’8’|’9’

<number> → {‘+’|’-‘}<digitstring>{’.’<digitsrting>}

<expression> → <term>

<expression>   →  <term> { ‘+’ |’-‘ <term>} 

 <term> → <factor>  

<term> → <factor>  {‘*’ |’/‘  <factor>}

<factor> → <identifier>  

<factor> → <number>  

<factor> → <identifier>|<number> ’^’ <identifier>|<number>

<factor> →’(‘ <expression>’)’ { ‘^’ <identifier>|<number>} ‘)’

<factor> →’(‘ <expression>’)’  ‘^’ ’(‘ <expression>’)’  

 

 

 

Your program must correctly handle all error conditions (and it must never crash!). You may use all available Java collections (including the mathematical library.^[5]

All identifiers  must be stored in a hash table. An identifier can be created or modified only via a assignment.  If a non-existing identifier is referenced, your program must return an error.

 

3          Submission instructions

Submit a single file named Expression.zip through Canvas that includes Calculator.java and CalculatorTest.java with your test cases..

 

Make sure that you test your code well!  Up to 20 points will be deducted for each of the following problems:

 

1) An ill-formed expression is not detected or a wrong error message is given; 2) The calculation result is wrong.

 

The code must be well-commented.

 

The code that does not compile will be found unacceptable.

 

 

 

[1] 𝑎                  and 𝑎^−𝑛 =       , where m and n are integers, and 𝑎⁰ =1.

𝑎_𝑛,

[2] Symbol “|” means or; in other words, a string on the either side of this symbol is a valid option.

[3] Any string inside the curly brackets is optional. For example, xyz can be an identifier.

[4] Any string inside the square brackets may be repeated a finite number of times.  (For example, a[x]a specifies this series of strings: axa, axxa, axxxa, etc.

[5] For instance to implement rational exponentiation a^b = e^{b ln a} you may use the Java Math methods for finding natural logarithms and exponentiation..