(without using java stack library HAVE TO MAKE OWN STACK)You are to write a Java
ID: 3820145 • Letter: #
Question
(without using java stack library 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).WITHOUT USING JAVA STACK***** ( HAVE TO MAKE OWN STACK).WITHOUT USING JAVA STACK***** ( HAVE TO MAKE OWN STACK).WITHOUT USING JAVA STACK***** ( HAVE TO MAKE OWN STACK).WITHOUT USING JAVA STACK***** ( HAVE TO MAKE OWN STACK).WITHOUT USING JAVA STACK***** ( HAVE TO MAKE OWN STACK).WITHOUT USING JAVA STACK***** ( HAVE TO MAKE OWN STACK).WITHOUT USING JAVA STACK***** ( HAVE TO MAKE OWN STACK).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
Stack : The Stack is an abstract data type that supports last-in-first-out (LIFO) stack of objects.
When a stack is first created, it contains no items.
The operation it will support:
1. new -> making a new stack
2. push -> insert an object
3. pop -> remove the top object
4. top -> give top object without removing it.
Supporting method are :
1. size -> size of stack.
2. isEmpty -> whether stack is empty or not.
Infix Expression:
Infix notation is the notation in which the operators are placed between the operands. It is commonly used in arithmetical and logical formulae and statements.
Eg: 2 + 2 * 5 / 8
Postfix Expression:
This is also called as Reverse Polish Notation. Here the operators are written after the operands.
Eg: 5 1 2 + 4 × + 3
The infix expression for the above example is 5 + ((1 + 2) × 4) 3.
To implement this in java with user defined stack is as follows:
public class StackApp {
public static class Stack<T> {
private int top = 0;
private final static int stackMax=100;
private Object[] stk = new Object[stackMax+1];
public Stack() { // constructor
}
public boolean isEmpty(){
if (top==0) return true;
else return false;
}
public void push(T el) {
if(top==stackMax)
System.out.println("Stack push overflow error");
else top=top+1;
stk[top]=el;
}
public T pop(){
if(isEmpty()){
System.out.println("Stack push underflow error");
return null;
}
else top=top-1;
return(T)stk[top+1];
}
public T top(){
if(isEmpty()){
//System.out.println("Stack empty");
return null;
}
else return (T)stk[top];
}
}
public static boolean isOperator(char c){
return(c=='+' || c=='-' || c=='/' || c=='*' || c=='^');
}
public static double evaluate(double x, char o, double y) {
double result=0;
switch(o) {
case '+' : result=x+y; break;
case '-' : result=x-y; break;
case '*' : result=x*y; break;
case '/' : result=x/y; break;
case '^' : result=Math.pow(x, y); break;
default : break;
}
return result;
}
public class InfixToPostfix {
private string input;
private string output;
public InfixToPostfix(String in) {
input = in;
int stackSize= input.length();
s = new Stack(stackSize);
}
public String doconvert() {
for (int j =0 ; j< input.length(); j++) {
char ch = input.charAt(j);
switch (ch) {
case '+':
case '-':
gotOp(ch, 1);
break;
case '*':
case '/':
gotOp(ch, 2);
break;
case '(':
s.push(ch);
break;
case ')':
gotPar(ch);
break;
default:
output = output + ch;
break;
}
}
While (!s.isEmpty()) {
Output = output + s.pop();
}
System.out.println(output);
return output;
}
public void gotOp(char opThis, int prec1) {
while (!s.isEmpty()) {
char opTop = s.pop();
if (opTop == '(') {
theStack.push(opTop);
break;
} else {
int prec2;
if (opTop == '+' || opTop == '-')
prec2 = 1;
else
prec2 = 2;
if (prec2 < prec1) {
s.push(opTop);
break;
}
else output = output + opTop;
}
}
s.push(opThis);
}
public void gotPar(char ch) {
while (!s.isEmpty()) {
char chl = s.pop();
if (chl == '(')
break;
else output = output + chl;
}
}
public static void main(String[] args) {
Scanner console=new Scanner(System.in);
Stack<Double> s=new Stack<Double>();
System.out.println("Input Infix form to evaluate:");
String input=console.nextLine();
String output;
char[] chararray=input.toCharArray();
double b,a;
InfixToPostfix convert = new InfixToPostfix(input);
output= convert.doconvert();
system.out.println("Postfix is " + output + ' ');
for(int i=0; i<chararray.length; i++) {
if(!isOperator(chararray[i]))
s.push((double)(chararray[i] - '0'));
else {
b=s.pop();
a=s.pop();
double c=evaluate(a, chararray[i], b);
s.push(c);
}
}
System.out.println(" " +s.pop());
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.