Prefix to postfix conversion using stack in java
Java program for Prefix to postfix conversion using stack. Here problem description and explanation.
// Java program for
// Prefix to postfix conversion
// Stack Node
class StackNode
{
public String data;
public StackNode next;
public StackNode(String data, StackNode top)
{
this.data = data;
this.next = top;
}
}
class MyStack
{
public StackNode top;
public int count;
public MyStack()
{
this.top = null;
this.count = 0;
}
// Returns the number of element in stack
public int size()
{
return count;
}
public boolean isEmpty()
{
if (this.size() > 0)
{
return false;
}
else
{
return true;
}
}
// Add a new element in stack
public void push(String data)
{
// Make a new stack node
// And set as top
this.top = new StackNode(data, this.top);
// Increase node value
this.count++;
}
// Add a top element in stack
public String pop()
{
String temp = "";
if (this.isEmpty() == false)
{
// Get remove top value
temp = this.top.data;
this.top = this.top.next;
// Reduce size
this.count--;
}
return temp;
}
// Used to get top element of stack
public String peek()
{
if (!this.isEmpty())
{
return top.data;
}
else
{
return "";
}
}
}
public class Conversion
{
// Check operator
public boolean isOperator(char text)
{
if (text == '+' || text == '-' ||
text == '*' || text == '/' ||
text == '^' || text == '%')
{
return true;
}
return false;
}
// Check operands
public boolean isOperands(char text)
{
if ((text >= '0' && text <= '9') ||
(text >= 'a' && text <= 'z') ||
(text >= 'A' && text <= 'Z'))
{
return true;
}
return false;
}
// Converting the given prefix expression to
// postfix expression
public void prefixToPostfix(String prefix)
{
// Get the size
int size = prefix.length();
// Create stack object
MyStack s = new MyStack();
// Some useful variables which is using
// of to storing current result
String auxiliary = "";
String op1 = "";
String op2 = "";
boolean isValid = true;
for (int i = size - 1; i >= 0; i--)
{
// Check whether given prefix location
// at [i] is an operator or not
if (isOperator(prefix.charAt(i)))
{
// When operator exist
// Check that two operands exist or not
if (s.size() > 1)
{
op1 = s.pop();
op2 = s.pop();
auxiliary = op1 + op2 + prefix.charAt(i);
s.push(auxiliary);
}
else
{
isValid = false;
}
}
else if (isOperands(prefix.charAt(i)))
{
// When get valid operands
auxiliary = "" + prefix.charAt(i);
s.push(auxiliary);
}
else
{
// Invalid operands or operator
isValid = false;
}
}
if (isValid == false)
{
// When have something wrong
System.out.println("Invalid Prefix : " + prefix);
}
else
{
// Display calculated result
System.out.println(" Prefix : " + prefix);
System.out.println(" Postfix : " + s.pop());
}
}
public static void main(String[] args)
{
Conversion task = new Conversion();
String prefix = "+*ab^cd";
task.prefixToPostfix(prefix);
prefix = "-+*^%adcex*y^ab";
task.prefixToPostfix(prefix);
}
}
Output
Prefix : +*ab^cd
Postfix : ab*cd^+
Prefix : -+*^%adcex*y^ab
Postfix : ad%c^e*x+yab^*-
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment