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

Question

这是我必须为我的数据结构类制作的 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. 正如 @SL Barth 提到的，while (theStack.topStk() != '('){ 行可能会导致堆栈下溢。您需要将其更改为：

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

2. 您还需要保护下面的 theStack.pop();：

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

3. 当您从堆栈顶部检查优先级时，您不应在输出中放置 '(' 字符：

   if (topSymb != '(') {
       后缀=后缀+topSymb；
   }
   

4. 但是 kicker 错误是，当您关闭 ')' 时，您将从堆栈中卸载到 int 中： int topStk = theStack.pop() ; 应该将其更改为输出 a 的 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 1, char 2) {
      返回 (charToPrcd(一) >= charToPrcd(二));
  }
  私有 int charToPrcd(char ch) {
      开关（通道）{
          case '+' : case '-' : 返回 1;
          case '*' : case '/' : 返回 2;
          case '
  

: 返回 3; case '(' : 返回 4; 默认：返回0； } }