infix to postfix conversion program(java)
https://stackoverflow.com//questions/12667574
-
11-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
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]);
}
}
}
Solution
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();
}
}
}
}
OTHER TIPS
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/)(+
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/
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.
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 : sankie2902@gmail.com
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
