Kanishka Jaiswal
Reputation: 27
infix to postfix conversion program(java)
I was working on a infix to postfix program(using stacks) but after all those efforts, something went wrong somewhere.I am getting the output as infix without conversion, please check if my intopost method is correct or not.
//stack class also containing the intopostfix method
import java.util.*;
public class Stack
{ int i,j;
char postfix[];
char stack[];
int top;
String post;
public Stack(int n)
{
stack=new char[n];
top=-1;
}
public void push(char item)
{
if(top>=stack.length)
System.out.println("Stack overflow");
else
{
stack[++top]=item;
}
}
public char pop()
{
if(top==-1)
{ System.out.println("Stack underflow");
return 0;
}
else
return stack[top--];
}
boolean isAlpha(char ch)
{
if((ch>='a'&&ch<='z')||(ch>=0&&ch<='9'))
return true;
else
return false;
}
boolean isOperator(char ch)
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
return true;
else return false;
}
void intopost(String str)
{
postfix=new char[str.length()];
char ch;
j=0;
for(i=0;i<str.length();i++)
{
ch=str.charAt(i);
if(ch=='(')
push(ch);
else if(isAlpha(ch))
{
postfix[j++]=ch;
}
else if(isOperator(ch))
{
push (ch);
}
else if(ch==')')
{
while((pop())!='(')
{
postfix[j++]=pop();
}
}
}
}
void disp()
{
for(i=0;i<postfix.length;i++)
{
System.out.print(postfix[i]);
}
}
}
Upvotes: 1
Views: 30469
Answers (5)
MADMEN
Reputation: 1
try this code, more efficient as here i am not making use of lots of methods in this, just the main method.
package inn;
import com.sun.org.apache.bcel.internal.generic.GOTO; import java.util.Scanner;
/** * * @author MADMEN */
public class Half_Life {
public Half_Life()
{
// a+b*c
// a*b+c
// d/e*c+2
// d/e*(c+2)
// (a+b)*(c-d)
// (a+b-c)*d/f
// (a+b)*c-(d-e)^(f+g)
// (4+8)*(6-5)/((3-2)*(2+2))
//(300+23)*(43-21)/(84+7) -> 300 23+43 21-*84 7+/
}
public static void main(String[] args)
{
System.out.print("\n Enter Expression : ");
Scanner c=new Scanner(System.in);
String exp=c.next();
int sym_top=0,po_top=-1,p=0,p2=0;
int size=exp.length();
char a[]=exp.toCharArray();
char symbols[]=new char[size];
char pfix[]=new char[size];
symbols[sym_top]='$';
for(int i=0;i<size;i++)
{
char c1=a[i];
if(c1==')')
{
while(sym_top!=0)
{
if(symbols[sym_top]=='(')
break;
pfix[++po_top]=symbols[sym_top--];
}
sym_top--;
}
else if(c1=='(')
{
symbols[++sym_top]=c1;
}
else if(c1=='+' || c1=='-' || c1=='*' || c1=='/' || c1=='^')
{
switch(c1)
{
case '+':
case '-': p=2;
break;
case '*':
case '/': p=4;
break;
case '^': p=5;
break;
default: p=0;
}
if(sym_top<1)
{
symbols[++sym_top]=c1;
}
else
{
do
{
char c2=symbols[sym_top];
if(c2=='^')
{
p2=5;
}
else if(c2=='*' || c2=='/')
{
p2=4;
}
else if(c2=='+' || c2=='-')
{
p2=2;
}
else
{
p2=1;
}
if(p2>=p)
{
pfix[++po_top]=symbols[sym_top--];
}
if(p>p2 || symbols[sym_top]=='$')
{
symbols[++sym_top]=c1;
break;
}
}while(sym_top!=-1);
}
}
else
{
pfix[++po_top]=c1;
}
}
for(;sym_top>0;sym_top--)
{
pfix[++po_top]=symbols[sym_top];
}
System.out.print("\n Infix to Postfix expression : ");
for(int j=0;j<=po_top;j++)
{
System.out.print(pfix[j]);
}
System.out.println("\n");
}
}
check the extreme last brace.
you can ask for more Data Structures programs at : [email protected]
Upvotes: 0
Niru
Reputation: 742
Try this code
/**
* Checks if the input is operator or not
* @param c input to be checked
* @return true if operator
*/
private boolean isOperator(char c){
if(c == '+' || c == '-' || c == '*' || c =='/' || c == '^')
return true;
return false;
}
/**
* Checks if c2 has same or higher precedence than c1
* @param c1 first operator
* @param c2 second operator
* @return true if c2 has same or higher precedence
*/
private boolean checkPrecedence(char c1, char c2){
if((c2 == '+' || c2 == '-') && (c1 == '+' || c1 == '-'))
return true;
else if((c2 == '*' || c2 == '/') && (c1 == '+' || c1 == '-' || c1 == '*' || c1 == '/'))
return true;
else if((c2 == '^') && (c1 == '+' || c1 == '-' || c1 == '*' || c1 == '/'))
return true;
else
return false;
}
/**
* Converts infix expression to postfix
* @param infix infix expression to be converted
* @return postfix expression
*/
public String convert(String infix){
String postfix = ""; //equivalent postfix is empty initially
Stack<Character> s = new Stack<>(); //stack to hold symbols
s.push('#'); //symbol to denote end of stack
for(int i = 0; i < infix.length(); i++){
char inputSymbol = infix.charAt(i); //symbol to be processed
if(isOperator(inputSymbol)){ //if a operator
//repeatedly pops if stack top has same or higher precedence
while(checkPrecedence(inputSymbol, s.peek()))
postfix += s.pop();
s.push(inputSymbol);
}
else if(inputSymbol == '(')
s.push(inputSymbol); //push if left parenthesis
else if(inputSymbol == ')'){
//repeatedly pops if right parenthesis until left parenthesis is found
while(s.peek() != '(')
postfix += s.pop();
s.pop();
}
else
postfix += inputSymbol;
}
//pops all elements of stack left
while(s.peek() != '#'){
postfix += s.pop();
}
return postfix;
}
This is taken from my blog here. Visit to get the complete code and see the each step of conversion in detail . Also note that here both parenthesis and exponent are also considered and can convert any expression.
Upvotes: 0
Rakesh Kalra
Reputation: 1
public class InfixToPostfix
{
private Stack stack;
private String infix;
private String output = "";
public InfixToPostfix(String input)
{
infix = input;
stack = new Stack(infix.length());
}
public String convertInfixToPostfix()
{
for(int index=0; index < infix.length(); index++)
{
char itemRead = infix.charAt(index);
switch(itemRead)
{
case '+':
case '-':
processOperator(itemRead, 1);
break;
case '*':
case '/':
processOperator(itemRead, 2);
break;
case '(':
stack.push(itemRead);
break;
case ')':
popStackTillOpenParenthesis();
break;
default:
output = output + itemRead;
break;
}
}
while( !stack.isEmpty() )
{
output = output + stack.pop();
}
return output;
}
public void processOperator(char infixOperator, int precedence)
{
while( !stack.isEmpty() )
{
char popedOpr = stack.pop();
if( popedOpr == '(' )
{
stack.push(popedOpr);
break;
}
else
{
int popedOprPrecedence;
if(popedOpr == '+' || popedOpr == '-')
popedOprPrecedence = 1;
else
popedOprPrecedence = 2;
if(popedOprPrecedence < precedence)
{
stack.push(popedOpr);
break;
}
else
output = output + popedOpr;
}
}
stack.push(infixOperator);
}
public void popStackTillOpenParenthesis()
{
while(!stack.isEmpty())
{
char popedOpr = stack.pop();
if( popedOpr == '(' )
break;
else
output = output + popedOpr;
}
}
}
Explanation of postfix notation, with algorithm and example is present at: http://www.thinkscholar.com/java/java-topics/infix-to-postfix/ http://www.thinkscholar.com/java/java-topics/infix-to-postfix/
Upvotes: 0
Debobroto Das
Reputation: 862
at first change the following line
if((ch>='a'&&ch<='z')||(ch>=0&&ch<='9'))
into
if((ch>='a'&&ch<='z')||(ch>='0' &&ch<='9'))
And then
else if(ch==')')
{
while((pop())!='(')
{
postfix[j++]=pop();
}
}
here you are calling the pop function twice. this causes your stack to underflow. that should be called once.
and finally try the following
void intopost(String str)
{
postfix=new char[str.length()];
char ch;
j=0;
for(i=0;i<str.length();i++)
{
ch=str.charAt(i);
if(ch=='(')
push(ch);
else if(isAlpha(ch))
{
postfix[j++]=ch;
}
else if(isOperator(ch))
{
push (ch);
}
else if(ch==')')
{
char c = pop();
while(c!='(')
{
postfix[j++]=c;
c= pop();
}
}
}
}
Upvotes: 1
Anshu
Reputation: 7853
Following program would do the job for you
import java.io.*;
class stack
{
char stack1[]=new char[20];
int top;
void push(char ch)
{
top++;
stack1[top]=ch;
}
char pop()
{
char ch;
ch=stack1[top];
top--;
return ch;
}
int pre(char ch)
{
switch(ch)
{
case '-':return 1;
case '+':return 1;
case '*':return 2;
case '/':return 2;
}
return 0;
}
boolean operator(char ch)
{
if(ch=='/'||ch=='*'||ch=='+'||ch=='-')
return true;
else
return false;
}
boolean isAlpha(char ch)
{
if(ch>='a'&&ch<='z'||ch>='0'&&ch=='9')
return true;
else
return false;
}
void postfix(String str)
{
char output[]=new char[str.length()];
char ch;
int p=0,i;
for(i=0;i<str.length();i++)
{
ch=str.charAt(i);
if(ch=='(')
{
push(ch);
}
else if(isAlpha(ch))
{
output[p++]=ch;
}
else if(operator(ch))
{
if(stack1[top]==0||(pre(ch)>pre(stack1[top]))||stack1[top]=='(')
{
push(ch);
}
}
else if(pre(ch)<=pre(stack1[top]))
{
output[p++]=pop();
push(ch);
}
else if(ch=='(')
{
while((ch=pop())!='(')
{
output[p++]=ch;
}
}
}
while(top!=0)
{
output[p++]=pop();
}
for(int j=0;j<str.length();j++)
{
System.out.print(output[j]);
}
}
}
class intopost
{
public static void main(String[] args)throws Exception
{
String s;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
stack b=new stack();
System.out.println("Enter input string");
s=br.readLine();
System.out.println("Input String:"+s);
System.out.println("Output String:");
b.postfix(s);
}
}
Output:
Enter input string
a+b*c
Input String:a+b*c
Output String:
abc*+
Enter input string
a+(b*c)/d
Input String:a+(b*c)/d
Output String:
abc*d/)(+
Upvotes: 1
Related Questions
- Infix to postfix conversion in java
- Infix to Postfix
- Infix to Postfix using stacks
- Postfix to Infix
- Postfix to Infix - Parenthesis
- infix to postfix in java using stack class
- Infix to Postfix Converter with parenthesis
- Getting wrong outputs in infix to postfix application with java
- Postfix evaluation in java with stack
- Converting infix expressions to postfix expressions