dunglangu

1. Introduction
The goal of this assignment is to implement the stack ADT using a linked list structure, and then learn how to evaluate a postfix arithmetic expression with a stack.

Note: You have to finish all C level, B level, and A level parts in order to get 10 point, finish both C level and B level parts in order to get 7 point, and finish C level parts in
order to get 4 point.

2. Your task
Normal arithmetic expressions like “2 + 3” are said to in infix notation. This means that the operator (for example, +) is between the operands (for example, 2 and 3).
In postfix notation, on the other hand, the operands come first and are followed by the operator. So, the postfix equivalent of “2 + 3” is “ 2 3 +”. For a more complicated example, the postfix equivalent of “12 + 8 - 5” is “12 8 + 5 -”. For this project, assume that all numbers and operators are white-space delimited. You can find some description
about postfix expression in 6.10 of the text book (page 275-277).
To evaluate a postfix arithmetic expression man can use the following algorithm:
Variables: Stask S(head):
Input: String s in format of postfix arithmetic expression

1. While (there are elements in s)
a. Read the next token X in s
i. If X is value the push(X)
ii. Else {
1. Y = pop();
2. Z = pop();
3. W = Z X Y;
4. push(W);
}
2. R = pop();
3. return R


2.1 C-level:
Write a class NumStack to implement the interface NumStackInterface. In this class, you should use a linked list to implement a stack (Do not use Java 's built-in linked list, you have to implement it by yourself). NumStackInterface is as follows:
public interface NumStackInterface{
// push a number node to the stack
public void push(double d);
//pop a number node out of the stack
//use EmptyStackException to give errors if necessary.
public double pop();
//test if the stack is empty
public boolean isEmpty();
// look at the number node at the top of the stack
//without removing it from the stack.
//use EmptyStackException to give errors if necessary.
public double peek();
}

Each node in the linked list is:
public class NumNode {
double num;
NumNode next;
public NumNode(double n){
// add your code here
}
}

In addition to the methods listed in NumStackInterface, add another method to NumStack: public double evaluatePostfix(String postfix). This method takes in a String of a postfix expression, and returns the expression’s value. You method should be able to evaluate the result of “+”, “-”, “*”, “/”. At this level, don't worry about error checking or formatting numbers nicely.
Use A4Test.java with the argument “c” to test some simple postfix expressions (you have 4 point if the step is good).

2.2 B-level:
Now you’ll check for errors in expressions. Any errors should generate an exception to be thrown. Declare it to be thrown from your evaluatePostfix method, and the B-level test should catch the exceptions.
• Check that only legal numbers are in the input. There should be at most one decimal point. Examples of illegal input include: 1..2, 3.3.4. This error should throw a IllegalArgumentException.
• Any undefined characters. Expressions should never contain character that are undefined, such as “$”, “&”, letters, etc. This error should also throw an IllegalArgumentException.
• Check for ill-formed postfix expressions. It is only valid to have an operator when (at least) two operands are available on the stack. Thus, expressions like “+” or “2 4 / *” or “3 5 + 7 + -” are illegal. You’ll be able to tell that an expression is ill-formed when an operator is read, but there are less than two operands to pop off the stack.

This error should throw an IllegalPostfixExpressionException. (This is not a builtin class,
you should extend it from RuntimeException.)
Use A4Test.java with the argument “b” to test some postfix expressions that have various
errors in them. (you have 7 point if the step is good)

2.3 A-level:
Create a new constructor for NumStack that takes String filename as an argument.
Write code that will read in from this file a list of Math library methods that the calculator should implement. The data in the file is of the form:
functionname1 numberofarguments1
functionname2 numberofarguments2
etc.
All the functions will be from the Math library, all of them will take either one or two numbers (doubles) as an argument, and all of them will return a double as their result.
You’ll have to keep track of which functions take one argument and which take two, so the expression evaluator knows how many operands to pop off the stack.
We do not expect you to know how to call Java functions on the fly, so we provide a class that does this (MathMethod.java). The constructor takes a method name and the number of arguments the method takes. The call() method takes the arguments as input in the form of a double[] array of size 1 or 2 and returns the result of applying the function as a double.
Use A4Test.java with the argument “a” to test some postfix expressions that have functions toDegrees, sin, abs, max and sqrt in them. (you have 9 point if the step is good)

2.4 Testing on your own:
You can use A4Test.java without any arguments to pass an arbitrary String to your evaluate postfix method. This way, you can test other expression and functions. (you have 10 point if the step is good).

Assignment Submission

Information regarding the procedure for submitting the assignment will be provided on CMS. The submission must include the complete code (NumNode.java, NumStack.java and IllegalPostfixExpressionException.java).

Thanks nhiều....

baobinhday

Vào đâu download nè