1

这是我必须为我的数据结构类制作的一个 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');
    }  
}
4

1 回答 1

2

这是一个有趣的练习。你非常接近，但这里有一些错误。我不得不调试代码并稍微旋转一下。

  1. 正如@SL Barth 提到的，该while (theStack.topStk() != '('){行可能导致堆栈下溢。您需要将其更改为：

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

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

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

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

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

  4. 但是踢球的错误是，int当您关闭: 时，您正在从堆栈中卸载到')':int topStk = theStack.pop(); 那应该更改为输出 a+而不是43. :-)

几个风格点：

  • 如前所述，使用Character.isDigit(ch)
  • 您应该使用 aStringBuilder()这样您就可以这样做，postfix.append(ch)而不是使用 many 构建字符串postfix + ch。[不寒而栗]
  • 我会将postfix字段设为convert()方法的本地以缩小范围。
  • == false说or被认为是不好的形式== 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;
    }
}
于 2011-10-06T16:42:30.933 回答