1

我正在研究后缀程序的中缀(使用堆栈),但经过所有这些努力,某处出现了问题。我将输出作为中缀而不进行转换,请检查我的 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]);
    }
}
}
4

5 回答 5

1

以下程序将为您完成工作

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/)(+
于 2012-10-01T04:58:48.470 回答
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();
                }
    }

在这里,您调用了 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();
                }
    }

}

}

于 2012-10-01T05:08:32.223 回答
0
    公共类 InfixToPostfix                  
    {
      私有堆栈堆栈;
      私有字符串中缀;
      私人字符串输出=“”;

      公共 InfixToPostfix(字符串输入)   
      {
        中缀=输入;
        堆栈 = 新堆栈(中缀。长度());
      }

      公共字符串 convertInfixToPostfix()      
      {
        for(int index=0; index < infix.length(); index++)
        {
          char itemRead = infix.charAt(index);

          开关(项目读取)
          {

          案例“+”:               
          案子 '-':
            processOperator(itemRead, 1);      
            休息;               

          案子 '*':               
          案子 '/':
            processOperator(itemRead, 2);      
            休息;               

          案子 '(':               
            stack.push(itemRead);   
            休息;

          案子 ')':               
            popStackTillOpenParenthesis();        
            休息;

          默认:                
            输出 = 输出 + 项目读取;
            休息;
          }  
        }  
        而(!stack.isEmpty())     
        {
          输出 = 输出 + stack.pop();
        }
        返回输出;                   
      }  

      public void processOperator(char infixOperator, int 优先级)
      {                                
        而(!stack.isEmpty())
        {
          char popedOpr = stack.pop();

          if( popedOpr == '(' )            
          {
            stack.push(popedOpr);      
            休息;
          }
          别的                          
          {
            int popedOprPrecedence;                 
            如果(popedOpr == '+' || popedOpr == '-')
              popedOprPrecedence = 1;
            别的
              popedOprPrecedence = 2;
            如果(popedOprPrecedence < 优先级)          
            {                       
              stack.push(popedOpr);   
              休息;
            }
            别的                       
              输出 = 输出 + popedOpr;  
          }  
        }  
        stack.push(infixOperator);        
      }  

      公共无效popStackTillOpenParenthesis()
      {                             
        而(!stack.isEmpty())
        {
          char popedOpr = stack.pop();
          if( popedOpr == '(' )     
            休息;
          别的
            输出 = 输出 + popedOpr;
        }  
      }  
    }

带有算法和示例的后缀符号解释见:http ://www.thinkscholar.com/java/java-topics/infix-to-postfix/ http://www.thinkscholar.com/java/java-topics /中缀到后缀/

于 2014-03-14T06:27:27.360 回答
0

试试这个代码

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

取自我的博客。访问获取完整代码并详细查看转换的每个步骤。另请注意,此处还考虑了括号和指数,并且可以转换任何表达式。

于 2014-05-06T17:32:09.067 回答
0

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

package inn;

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

/** * * @作者疯子 */

公共课半条命{

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

于 2014-11-01T13:21:49.783 回答