Infix to postfix conversion of regular expression | Set 1
import java.util.Stack;
class InfixToPostfix {
static String toPostfix(String infix) {
// stack to store operators
Stack stack = new Stack<>();
StringBuilder result = new StringBuilder(); // store final result
int i = 0;
while(i < infix.length()) {
char ch = infix.charAt(i);
if(isOperand(ch)) {
// if it's operand then add into result
result.append(ch);
i++;
} else {
// deal with operator
if(stack.empty() || getPrecedence(ch) > getPrecedence(stack.peek())) {
// precendence of input operator is greater than operator
// at stack top then add input operator to stack
stack.push(ch);
i++;
} else {
// precendence of input operator is <= precendence of stack top
// operator so pop stack and add into result
result.append(stack.pop());
}
}
}
// pop out whatever is left in stack and insert into result
while(!stack.empty()) {
result.append(stack.pop());
}
return result.toString();
}
private static boolean isOperand(char ch) {
switch(ch){
case '+':
case '-':
case '*':
case '/':
return false;
}
return true;
}
private static int getPrecedence(char ch) {
switch(ch){
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
return 0;
}
public static void main (String[] args) {
String infix = "a+b*c-d/e";
System.out.println("Infix : " + infix + ", Postfix : " + toPostfix(infix));
}
}
Output
Infix : a+b*c-d/e, Postfix : abc*+de/-
Comments
Post a Comment