IN JAVA: For this lab we will be building an expression translator to convert in
ID: 3820495 • Letter: I
Question
IN JAVA:
For this lab we will be building an expression translator to convert infix notation to postfix notation. Typical expressions to be evaluated are as follows:
An algorithm to accomplish the transformation is:
R1: Initially the operatorStack is empty
R2: For each operator of the infix string loop until the operator has been pushed onto the operatorStack:
If the operatorStack is empty or the operator has a higher precedence than the operator on the top of the operatorStack then push the operator onto the operatorStack
else pop the operatorStack and append that popped operator to the postfix string
R3: Once the end ot the input string is encountered
loop until the operatorStack is empty: Pop the operatorStack and append that popped operator to the postfix string
infix expression postfix expression a + b - c a b + c - a - b + c * d a b - c d * + a + c - h / b * r a c + h b / r * - a + ( c - h ) / ( b * r ) a c h - b r * / +Explanation / Answer
import java.io.IOException;
public class InToPost {
private Stack theStack;
private String input;
private String output = "";
public InToPost(String in) {
input = in;
int stackSize = input.length();
theStack = new Stack(stackSize);
}
public String doTrans() {
for (int j = 0; j < input.length(); j++) {
char ch = input.charAt(j);
switch (ch) {
case '+':
case '-':
gotOper(ch, 1);
break;
case '*':
case '/':
gotOper(ch, 2);
break;
case '(':
theStack.push(ch);
break;
case ')':
gotParen(ch);
break;
default:
output = output + ch;
break;
}
}
while (!theStack.isEmpty()) {
output = output + theStack.pop();
}
return output;
}
public void gotOper(char opThis, int prec1) {
while (!theStack.isEmpty()) {
char opTop = theStack.pop();
if (opTop == '(') {
theStack.push(opTop);
break;
} else {
int prec2;
if (opTop == '+' || opTop == '-')
prec2 = 1;
else
prec2 = 2;
if (prec2 < prec1) {
theStack.push(opTop);
break;
}
else output = output + opTop;
}
}
theStack.push(opThis);
}
public void gotParen(char ch) {
while (!theStack.isEmpty()) {
char chx = theStack.pop();
if (chx == '(')
break;
else output = output + chx;
}
}
class Stack {
private int maxSize;
private char[] stackArray;
private int top;
public Stack(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);
}
}
public static void main(String[] args) throws IOException {
String input = "a + ( c - h ) / ( b * r )";
String output;
InToPost theTrans = new InToPost(input);
output = theTrans.doTrans();
System.out.println("Infix: " + input);
System.out.println("Postfix: " + output);
}
}