(WITHOUT USING JAVA STACK***** HAVE TO MAKE OWN STACK!!!!) (WITHOUT USING JAVA S
ID: 3818998 • Letter: #
Question
(WITHOUT USING JAVA STACK***** HAVE TO MAKE OWN STACK!!!!)
(WITHOUT USING JAVA STACK***** HAVE TO MAKE OWN STACK!!!!)
You are to write a Java program that allows the user to type in a mathematical formula at the keyboard and produces the answer on the screen WITHOUT USING JAVA STACK***** ( HAVE TO MAKE OWN STACK).
The formula will be typed in INFIX notation and will include only positive integers for the numbers. The operators that are acceptable are the following: + (plus), - (minus), * (multiply), / (divide), and ^ (power). Parenthesis are also allowed.
You should allow the user to type in the equation of his choice and then display the answer on the screen. Display a real answer. (for example: 3 / 2 = 1.5, NOT 1)
ALSO DISPLAY THE POST-FIX EQUATION ON THE SCREEN.
The normal rules of mathematics apply (parenthesis have the highest precedence followed by the ^, followed by * and /, followed by - and +).
Do not allow the program to bomb and warn the user if the equation is wrong. For example: 2 + 43 / * 12 cannot be calculated because there are too many operators.
When I test the program, I will only type positive integers as input and you can assume the input equation is valid.
Hints: You should treat the equation as a queue of tokens and read the tokens from the queue one at a time. Convert the INFIX equation to a POSTFIX equation. Then resolve the POSTFIX equation.
Sample equations-> Postfix
12 +(2 – 4 ) /5 ->12 2 4 – 5 / +
43 + 3^4 * 2 / 34 – 9 ->43 3 4 ^ 2 * 34 / + 9 -
2 ^ 4+34 - 3 ->2 4 ^ 34 + 3 -
Here are 2 String methods that will come in handy: replaceAll and split. Example of program running:
Enter an equation: 12+ (6- 4 ) ^ (1+1) / 2
RPN: 12 6 4 – 1 1 + ^ 2 / +
Answer: 14
Explanation / Answer
Hi Please see below the class to convert an infix equation to postfix and then to evaluate postfix equation.
Please comment for any queries/feedbacks.
Thanks
InfixPostfix.java
import java.util.*;
public class InfixPostfix{
private static final char ADD = '+', SUBTRACT = '-';
private static final char MULTIPLY = '*', DIVIDE = '/';
private static final char POWER ='^';
public InfixPostfix(){
}
// Private methods:
private boolean isOperator(char c) { // Tell whether c is an operator.
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'
|| c=='(' || c==')';
}//end isOperator
private boolean isSpace(char c) { // Tell whether c is a space.
return (c == ' ');
}//end isSpace
private boolean lowerPrecedence(char op1, char op2) {
// Tell whether op1 has lower precedence than op2, where op1 is an
// operator on the left and op2 is an operator on the right.
// op1 and op2 are assumed to be operator characters (+,-,*,/,^).
switch (op1) {
case '+':
case '-':
return !(op2=='+' || op2=='-') ;
case '*':
case '/':
return op2=='^' || op2=='(';
case '^':
return op2=='(';
case '(': return true;
default: // (shouldn't happen)
return false;
}
} // end lowerPrecedence
// Method to convert infix to postfix:
public String convertToPostfix(String infix) {
Stack operatorStack = new Stack();
char c;
StringTokenizer parser = new StringTokenizer(infix,"+-*/^() ",true);
StringBuffer postfix = new StringBuffer(infix.length());
while (parser.hasMoreTokens()) {
String token = parser.nextToken();
c = token.charAt(0);
if ( (token.length() == 1) && isOperator(c) ) {
while (!operatorStack.empty() &&
!lowerPrecedence(((String)operatorStack.peek()).charAt(0), c))
postfix.append(" ").append((String)operatorStack.pop());
if (c==')') {
String operator = (String)operatorStack.pop();
while (operator.charAt(0)!='(') {
postfix.append(" ").append(operator);
operator = (String)operatorStack.pop();
}
}
else
operatorStack.push(token);
}
else if ( (token.length() == 1) && isSpace(c) ) {
}
else {
postfix.append(" ").append(token);
}
}
while (!operatorStack.empty())
postfix.append(" ").append((String)operatorStack.pop());
return postfix.toString();
}
public int evaluate(String expr) {
// assert (isValid(expr));
Stack stack = new Stack();
int op1, op2, result = 0;
String token;
StringTokenizer tokenizer = new StringTokenizer(expr);
while (tokenizer.hasMoreTokens()) {
token = tokenizer.nextToken();
char c = token.charAt(0);
if (isOperator(c)) {
op2 = ((Integer) stack.pop()).intValue();
op1 = ((Integer) stack.pop()).intValue();
result = evalSingleOp(token.charAt(0), op1, op2);
stack.push(new Integer(result));
}
else
stack.push(new Integer(Integer.parseInt(token)));
}
result = ((Integer) stack.pop()).intValue();
return result;
}
private int evalSingleOp(char operation, int op1, int op2) {
int result = 0;
switch (operation) {
case ADD :
result = op1 + op2;
break;
case SUBTRACT :
result = op1 - op2;
break;
case MULTIPLY :
result = op1 * op2;
break;
case DIVIDE :
result = op1 / op2;
break;
case POWER :
result = (int) Math.pow(op1,op2);
break;
}
return result;
}
public static void main(String[] args) { // Test method for the class.
Scanner scan = new Scanner(System.in);
System.out.println("Enter an equation: ");
String testString = scan.nextLine();
InfixPostfix converter = new InfixPostfix();
System.out.println(" Test for convertToPostfix: ");
System.out.println("infix: " + testString);
System.out.println("postfix: " + converter.convertToPostfix(testString));
System.out.println("postfix evaluation: " + converter.evaluate( converter.convertToPostfix(testString)));
System.out.println();
} // end main
}//end class InfixToPostfix
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.