Assume an infix expression can only contain five operators, * / % + -, left and

Question

Assume an infix expression can only contain five operators, * / % + -, left and right parenthesis, and variables or numbers (can be negative). Operators and operands are separated by white spaces, and there is no space between negative sign and its following operand. Implement this java method, public static String infixToPostFix(String infixExp), using the following algorithm: Use a stack to store operators. If an item is popped from the stack, it will be appended to the output if it is not a parenthesis. When an operand is read, append it to the output When a right parenthesis is read, pop entries from the stack until a (corresponding) left parenthesis is reached, which is then popped but not appended to the output. If any other symbol is read, pop entries from the stack until an entry of lower priority is reached, then the new operator is pushed on the to stack. Left parenthesis has the highest priority. If it is the end of input, pop entries from the stack until it is empty.

Explanation / Answer

// Program to convert infix expression to postfix expression
import java.io.IOException; // imporing ioexception pacakeage
public class infixtopostfix { // main class
// variable declarations
private Stack St; // stack varibale
private String infix; // i/p string
private String postfix = ""; // o/p variable, initially empty
public infixtopostfix(String in) { // constructor
infix = in; // initalising i/p with the value passed through in variable
int insize = infix.length(); // finding its length and storing in insize variable
St = new Stack(insize); // creating object for stack, st with size of the i/p expression lenghth
}
public String infixToPostFix(String infixExp) { // method for converting infix to postfix
for (int j = 0; j < infixExp.length(); j++) { // reading each character in the expression
char ch = infixExp.charAt(j); // stroing every time in variable ch
switch (ch) { // checking weather it is operand, operator or paranthesis
case '+': // if it is + or -
case '-':
Operpre(ch, 1); // assinging it preference as 1 and calling Operpre function passing the character and its preference
break;
case '*':
case '/':
Operpre(ch, 2); // if * or / assigning its preference as 2 and calling Operpre function passing the character and its preference
break;
case '(':
St.push(ch); // if it is open parenthesis push it into stack
break;
case ')':
Parenpar(); // if it is closed parenthesis call function Prenpar to pop untill open parenthesis
break;
default:
postfix = postfix + ch; // or if it is operand add to output
break;
}
}
while (!St.isEmpty()) { // after reading all the characters in input pop all elements and add to stack untill stack becomes empty
postfix = postfix + St.pop();
}
return postfix; // return that postfix expression
}
public void Operpre(char currop, int prec1) { // function to push operators into stack with arguments currop (current operator) and prec1 (its precedence)
while (!St.isEmpty()) { // untill stack is empty
char top = St.pop(); // pop the top element
if (top == '(') { // if top is open bracket
St.push(top); // push it into stack
break;
} else {
int prec2; // preference of the top of stack
if (top == '+' || top == '-') // if it is + or -
prec2 = 1; // preference is 1
else
prec2 = 2; // else 2
if (prec2 < prec1) { // if the preference of top is less than the preference of the read character   
St.push(top); // push the top again into stack
break;
}
else postfix = postfix + top; // or add to output
}
}
St.push(currop); // and atlast push the current operator to stack
}
public void Parenpar() { // function to pop elements until open paranthesis occur when closed paranthesis is read
while (!St.isEmpty()) { // untill stack is empty
char ch = St.pop(); // pop and store it in chx variable
if (ch == '(') // if chax is open paranthesis then break the while
break;
else postfix = postfix + ch; // else add that operator to output
}
}
public static void main(String[] args) throws IOException { // main method
String infix = "1+2*4/5-7+3/6"; // i/p string
String postfix; // output varaiable declaration
infixtopostfix intopo = new infixtopostfix(infix); // creating object for the main class
postfix = intopo.infixToPostFix(infix); // calling method to convert infix expression to postfix expression passing the infix expression to it
System.out.println("Postfix is " + postfix + ' '); // printing the postfix expression
}
class Stack { // class for stack
private int stsize; // variable for size of stack
private char[] starray; // stack array
private int top; // variable of top of stack
public Stack(int max) { // method to create stacvk array with size passed to the menthod
stsize = max;
starray = new char[stsize];
top = -1;
}
public void push(char j) { // function to push an element into stack
starray[++top] = j;
}
public char pop() { // function to pop an element from stack
return starray[top--];
}
public char peek() {// function to know the top of the stack
return starray[top];
}
public boolean isEmpty() {// function to know whether the stack is empty or not
return (top == -1);
}
}
}

o/p:

124*5/+7-36/+

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.