CISS-111 Project 7
Write a Java program to demonstrate using stacks. This project will use two stacks to evaluate infix arithmetic expressions. This will act similar to the way the Java compiler may evaluate simple expressions. The GenericStack object being created will be a generic object.
Given:
You will need for Project 7:
public static int eval(String s)A method to completely evaluate a single expression in the form of a String. |
public static void apply(GenStack<Integer> val, GenStack<Character> op)A method to apply a single binary operation. This methods takes an operator from op along with two values from val and performs the operation. The result is pushed back onto val. |
public static int prec(char op)A method to determine operator precedence. |
Take the GenStack code from Chapter 17.
Some important details:
- Expressions will not cross line boundaries.
- All expression evaluation will occur in the
eval()method where you will have two stacks: an operator stack and a value stack. - Expressions will have the following components:
- Integers
- Binary Operators {*, /, %, +, -}.
- Parentheses for altering precedence.
- Whitespace which can be ignored.
- All expressions are considered to be correct in syntax.
- Precedence rules are the same as for Java. Parentheses {(, )}first, then {*, /, %} and lastly {+, -}. Operators of like precedence are evaluated from left to right.
- You should pass
prec()the operator and have it return an integer. This is so you can compare the precedence of the operator on the stack with the one from the input stream. - Be certain to
apply()whatever is left on the value and operator stacks once the expression in its string form has been exhausted. The result will be the only value left on the value stack.
Based on the data file, your results should look something like:
45+ 312* 2-300 = 369 2 +3 * 4 = 14 (2 +3) * 4 = 20 (((3 + 2)*6) % 4 ) = 2 (( 40 + 55) / 2 ) + ( 2* ( 2 + 1)) = 53 3 - (4+5*6-77) / 4 = 13 (( ( ( ( ( ( ( ( ( 2-4)*3)/3) - 50)%3) *423)/20)-100) +564)% 4) = 3
Consider the following evaluation rules when building your program:
The rules for the evaluation of expressions are as follows:
| Category | What to do. |
|---|---|
| ( |
push onto operator stack |
| value |
push value onto value stack (This includes variables. Look them up during apply().) |
| ) |
while (top operator stack != '(')
apply
pop '(' from operator stack
|
| arithmetic operator |
while (! empty operator stack && (prec(currop) <= prec(top operator stack))) apply push currop |
| assignment operator |
push currop |
| end of string |
while (! empty operator stack) apply result remains on value stack |
Extra Credit #1
For 3 additional points, allow unary + and – operators.
-1 * -4 + 32 - -6
would produce
-1 * -4 + 32 - -6 = 42
Extra Credit #2
For 5 additional points, Allow for assignment operators. Using a HashMap, keep track of variables and allow for substitution in expressions.
x = 4 + 3 * 2 y = x * 2 32 + x + y
Sample output would be
32 + x + y = 62
Submit the project to the Learning Management System as Project7_lastname.java.