Programa de conversión de infijo al postfix (Java)
https://stackoverflow.com//questions/12667574
-
11-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estaba trabajando en un programa de infijo al postfix (usando pilas), pero después de todos esos esfuerzos, algo salió mal en algún lugar. Estoy obteniendo la salida como infijo sin conversión, verifique si mi método de intopost es correcto o no.
//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]);
}
}
}
Solución
al principio cambiar la siguiente línea
if((ch>='a'&&ch<='z')||(ch>=0&&ch<='9'))
en
if((ch>='a'&&ch<='z')||(ch>='0' &&ch<='9'))
y luego
else if(ch==')')
{
while((pop())!='(')
{
postfix[j++]=pop();
}
}
Aquí está llamando a la función POP dos veces.Esto hace que su pila se suba. que debe llamarse una vez.
y finalmente intente lo siguiente
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();
}
}
}
}
Otros consejos
El siguiente programa haría el trabajo para usted
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;
}
}
}
Explicación de la notación de Postfix, con algoritmo y ejemplo está presente en: >http://www.thinkscholar.com/java/java-topics/infix-to-postfix/ http://www.thinkscholar.com/java/java-topics/infijo a-postfix /
Pruebe este código
/**
* 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;
}
Esto se toma de mi blog aquí .Visita para obtener el código completo y ver cada paso de la conversión en detalle.También tenga en cuenta que aquí también se consideran paréntesis y exponente y pueden convertir cualquier expresión.
Pruebe este código, más eficiente como aquí no estoy haciendo uso de muchos métodos en esto, solo el método principal.
package inn;
Importar com.sun.org.apache.bcel.internal.genic.goto; Importar java.util.Scanner;
/ ** * * @Author Madmen * /
Clase pública 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");
}
}
Revise la última abrazadera extrema.
Puede solicitar más programas de estructuras de datos en: sankie2902@gmail.com
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
