中缀后缀转换程序（java）

Question

我正在为后缀程序（使用堆栈）中缀工作，但经过所有这些努力，出现了某处某处出错。我得到输出作为中缀而无需转换，请检查我的intopost方法是否正确。

//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]); 
    } 
} 
} 

Answer 1

首先更改以下行

if((ch>='a'&&ch<='z')||(ch>=0&&ch<='9')) 

到

if((ch>='a'&&ch<='z')||(ch>='0' &&ch<='9')) 

然后

else if(ch==')') 
    { 
     while((pop())!='(') 
       { 
        postfix[j++]=pop(); 
       } 
    } 

这里您要调用两次弹出功能。这会导致您的堆栈下溢。应该被调用一次的 。

最后尝试后缀符号的下面

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(); 
       } 
    } 

} 

}

Answer 2

下面的程序将做的工作适合你

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/)(+ 

Answer 3

 

    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; 
     } 
     } 
    } 

说明，用算法和实例存在于：http://www.thinkscholar.com/java/java-topics/infix-to-postfix/ http://www.thinkscholar.com/java/java-topics/infix-to-postfix/

Answer 4

尝试此代码

/** 
    * 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; 
} 

这取自我的博客here。访问以获取完整的代码并详细了解转换的每一步。还要注意，这里括号和指数也被考虑并且可以转换任何表达式。

Answer 5

试试这个代码，效率更高，因为在这里我没有使用很多方法，只是主要的方法。

package inn; 

import com.sun.org.apache.bcel.internal.generic.GOTO; import java.util.Scanner;

/** * * @author疯子 */

公共类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"); 
} 

}

检查极致最后一个大括号。

你可以要求更多的数据结构课程：sankie2902@gmail.com