Last active
August 29, 2015 14:05
-
-
Save KodeSeeker/b26f9b9c717376e05c28 to your computer and use it in GitHub Desktop.
Postfix to Infix Notation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Convert from Postfix to Infix Notation | |
* Infix to Postfix :https://gist.github.com/KodeSeeker/f776c5477c3be3f43a77 | |
* Algo: | |
* 1) Walk through postfix expression | |
* 2) If input is a num then push to stack. | |
* 3) If the input is a operator then pop the last two operatonds from stack and perform operation. Push result back onto stack. | |
* | |
* Error condition : if you see a operator and there arent 2 operands in the left in the stack. | |
* | |
* To reduce the paranthesis: Add a parenthesis ONLY if the operator you encounter has a higher precedence than the current major | |
* operator in the expression(on the stack.) | |
* */ | |
public String postFixtoInfix(String infix) | |
{ | |
if (infix==null) | |
return null; | |
Stack<Expression> ops= new Stack<Expression>(); | |
for(Character c:infix.tocharArray()) | |
{ | |
if(!c.isOperator()) | |
{ | |
ops.push(c); | |
} | |
else | |
{ | |
Operator o= new Operator(c); // assume there is an Operator object. | |
/** | |
if(ops.peek().isExpression()) | |
{ | |
//compare its operator to the current operator and update it if its LESSER precedence than the current operator | |
Expression e= ops.pop(); | |
if (e.getOperator().precedence< o.precedence) | |
{ | |
o.precedence=e.getOperator().precedence; | |
e.ExpValue="("+ e.getExpValue+")" | |
} | |
ops.push(e); | |
} | |
else{**/ | |
if (ops.pop()!=null) | |
String op1= ops.pop(); | |
if (ops.pop()!=null) | |
String op2= ops.pop(); | |
else | |
{ | |
throw new StackUnderFlowException(); | |
} | |
Expression interim= new Expression(); | |
interim.value= op1+o.getValue()+op2;// string concatenation | |
interim.opvalue=op1.getValue(); | |
/* if(interim.opvalue < o.getValue()) | |
interim="("+interim+")"; //Need to handle brackets. | |
interim.opvalue=o.getValue(); | |
*/ | |
ops.push(interim); | |
} | |
} | |
return ops.pop().toString();// final expression. | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment