Skip to content

Instantly share code, notes, and snippets.

@KodeSeeker
Last active August 29, 2015 14:05
Show Gist options
  • Save KodeSeeker/b26f9b9c717376e05c28 to your computer and use it in GitHub Desktop.
Save KodeSeeker/b26f9b9c717376e05c28 to your computer and use it in GitHub Desktop.
Postfix to Infix Notation
/**
* 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