(WITHOUT USING JAVA STACK***** HAVE TO MAKE OWN STACK!!!!) You are to write a Ja
ID: 3818902 • Letter: #
Question
(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
package dec7;
import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Pattern;
public class InFixToPostFix {
private Stack1 stack1;
private String inFixExpression;
private String postFixExpression = "";
private String expression;
private Stack<Double> nums;
public static final Pattern CHARACTER = Pattern.compile("\S.*?");
public static final Pattern OPERATOR = Pattern
.compile("((\d+\.?\d*)|(\.\d+))([Ee][-+]?\d+)?.*?");
public InFixToPostFix(String in) {
inFixExpression = in;
int stackSize = inFixExpression.length();
stack1 = new Stack1(stackSize);
nums = new Stack<Double>();
expression = "";
}
public void calculate(String n) {
if (nums.size() < 2)
throw new IllegalArgumentException("Input expression: "
+ expression + " invalid");
double op2 = nums.pop();
double op1 = nums.pop();
char op = n.charAt(0);
switch (op) {
case '^':
nums.push(Math.pow(op1, op2));
break;
case '+':
nums.push(op1 + op2);
break;
case '-':
nums.push(op1 - op2);
break;
case '*':
nums.push(op1 * op2);
break;
case '/':
nums.push(op1 / op2);
break;
default:
System.out.println("What is this? " + op);
}
}
public double getResult() {
if (nums.size() > 1 || nums.isEmpty())
throw new IllegalArgumentException("Input expression: "
+ expression + " invalid");
return (double) nums.pop();
}
public void setExpression(String e) {
expression = e;
}
public void evalPostfix() {
Scanner expression = new Scanner(this.expression);
String next;
do {
if (expression.hasNext(OPERATOR)) {
next = expression.findInLine(OPERATOR);
nums.push(new Double(next));
} else {
next = expression.findInLine(CHARACTER);
calculate(next);
}
} while (expression.hasNext());
}
public String doPostFixExpression() {
for (int j = 0; j < inFixExpression.length(); j++) {
char ch = inFixExpression.charAt(j);
switch (ch) {
case '^':
gotOper(ch, 3);
break;
case '+':
case '-':
gotOper(ch, 1);
break;
case '*':
case '/':
gotOper(ch, 2);
break;
case '(':
stack1.push(ch);
break;
case ')':
gotParen(ch);
break;
default:
postFixExpression = postFixExpression + ch;
break;
}
}
while (!stack1.isEmpty()) {
postFixExpression = postFixExpression + stack1.pop();
}
System.out.println(postFixExpression);
return postFixExpression;
}
public void gotOper(char opThis, int prec1) {
while (!stack1.isEmpty()) {
char opTop = stack1.pop();
if (opTop == '(') {
stack1.push(opTop);
break;
} else {
int prec2;
if (opTop == '+' || opTop == '-')
prec2 = 1;
else if (opTop == '*' || opTop == '/')
prec2 = 2;
else
prec2 = 3;
if (prec2 < prec1) {
stack1.push(opTop);
break;
} else
postFixExpression = postFixExpression + opTop;
}
}
stack1.push(opThis);
}
public void gotParen(char ch) {
while (!stack1.isEmpty()) {
char chx = stack1.pop();
if (chx == '(')
break;
else
postFixExpression = postFixExpression + chx;
}
}
public static void main(String[] args) throws IOException {
Scanner kb = new Scanner(System.in);
System.out.print("Enter an equation: ");
String input = kb.nextLine();
InFixToPostFix theTrans = new InFixToPostFix(input);
String postFix = theTrans.doPostFixExpression();
System.out.println("RPN: " + postFix + ' ');
theTrans.setExpression(postFix);
theTrans.evalPostfix();
System.out.println("Answer: " + theTrans.getResult());
}
}
class Stack1 {
private int maxSize;
private char[] stackArray;
private int top;
public Stack1(int max) {
maxSize = max;
stackArray = new char[maxSize];
top = -1;
}
public void push(char j) {
stackArray[++top] = j;
}
public char pop() {
return stackArray[top--];
}
public char peek() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
}
OUTPUT:
Enter an equation: 12+ (6- 4 ) ^ (1+ 1) / 2
12 6 4 - 1 1+ ^ 2/+
RPN: 12 6 4 - 1 1+ ^ 2/+
Answer: 14.0
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.