java - 识别中缀到后缀转换中的括号

Question

这个问题已经有答案了:

Handling parenthesis while converting infix expressions to postfix expressions (2 个回答)

已关闭 6 年前。

这是我必须为我的数据结构类创建的 java 类。我知道这远不是进行转换的最佳方法，但它脱离了他在类里面给出的伪代码，因此正是他所寻找的。他留给我们的唯一需要我们自己解决的问题是算法如何识别括号。当我输入没有它们的表达式时，程序运行得很好，但是当我添加括号时，程序将无法运行，具体来说，通过一些调试，我发现右括号会执行此操作“)”。我用注释标记了该方法的实际括号部分所在的位置。感谢您的帮助!

public class InToPost {
    private Stack theStack;
    private String infix;
    private String postfix = "";

    public InToPost(String in) {
        infix = in;
        int stackSize = infix.length();
        theStack = new Stack(stackSize);
    }

    public String convert(){
        for (int i = 0; i < infix.length(); i++) {
            char ch = infix.charAt(i);
            if ((ch == '0') || (ch == '1') || (ch == '2') || (ch == '3') || (ch == '4') ||
                (ch == '5') || (ch == '6') || (ch == '7') || (ch == '8') || (ch == '9')) {
                postfix = postfix + ch;
            }
            //check for parenthesis
            else if (ch == ')'){
                while (theStack.topStk() != '('){
                    int topStk = theStack.pop();
                    postfix = postfix + topStk;
                }
                theStack.pop();
            } else {
                while ((theStack.isEmpty() == false)&&(prcd(theStack.topStk(),ch) == true)){
                    char topSymb = theStack.pop();
                    postfix = postfix + topSymb;
                }
                theStack.push(ch);
            }
        }
        while(theStack.isEmpty() == false){
            char topSymb = theStack.pop();
            postfix = postfix + topSymb;
        }
        return postfix;
    }

    public boolean prcd(char one, char two){
        int onePrcd = 0;
        int twoPrcd = 0;
        if ((one == '+') || (one == '-')){
            onePrcd = 1;
        }
        if ((two == '+') || (two == '-')){
            twoPrcd = 1;
        }
        if ((one == '*') || (one == '/')){
            onePrcd = 2;
        }
        if ((two == '*') || (two == '/')){
            twoPrcd = 2;
        }
        if (one == '$') {
            onePrcd = 3;
        }
        if (two == '$') {
            twoPrcd = 3;
        }
        if (one == '(') {
            onePrcd = 4;
        }
        if (two == '('){
            twoPrcd = 4;
        }
        if (onePrcd >= twoPrcd){
            return true;
        } else {
            return false;
        }
    }
    public static void main(String[] args){
        String input = "(2+3)*4";
        String output;
        InToPost theTrans = new InToPost(input);
        output = theTrans.convert(); 
        System.out.println("Postfix is " + output + '\n');
    }  
}

Answer 1

这是一个有趣的练习。你已经很接近了，但是这里有一些错误。我必须调试代码并稍微调整一下。

1. 作为@S.L.巴特提到，while (theStack.topStk() != '('){行可能会导致堆栈下溢。您需要将其更改为:

   while (!theStack.isEmpty() && theStack.topStk() != '('){

2. You'll also need to protect the theStack.pop(); right below there:

   if (!theStack.isEmpty()) {
       theStack.pop();
   }
   

3. 当您从堆栈顶部检查优先级时，不应输入 '('输出中的字符:

   if (topSymb != '(') {
       postfix = postfix + topSymb;
   }
   

4. 但是引发的错误是您正在从堆栈卸载到 int当您关闭')'时:int topStk = theStack.pop();应该将其更改为输出 + 的 char而不是43 。 :-)

几个风格点:

• 如上所述，请使用 Character.isDigit(ch)
• 您应该使用StringBuilder()所以你可以做postfix.append(ch)而不是用许多 postfix + ch 构建字符串。 [颤抖]
• 我会做postfix convert() 的本地字段缩小范围的方法。
• 说 == false 被认为是不好的形式。或== true 。只需删除 == true并使用 ! false 字符:(!theStack.isEmpty()) && prcd(theStack.topStk(),ch)

• 我会创建一个 charToPrecedence(char)它使用开关返回每个字符的值。代码更加简洁。

  public boolean precident(char one, char two) {
      return (charToPrcd(one) >= charToPrcd(two));
  }
  private int charToPrcd(char ch) {
      switch (ch) {
          case '+' : case '-' : return 1;
          case '*' : case '/' : return 2;
          case '$' : return 3;
          case '(' : return 4;
          default : return 0;
      }
  }