java - 使用 Stacks Java 中缀到 Postfix

Question

我正在尝试编写一个程序将中缀表达式转换为后缀表达式。

我使用的算法如下:

1. Create a stack
2. For each character t in the expression
   - If t is an operand, append it to the output
   - Else if t is ')',then pop from the stack till '(' is encountered and append 
     it to the output. do not append '(' to the output.
   - If t is an operator or '('
        -- If t has higher precedence than the top of the stack, then push t 
           on to the stack.
        -- If t has lower precedence than top of the stack, then keep popping 
           from the stack and appending to the output until either stack is 
           empty or a lower priority operator is encountered.

    After the input is over, keep popping and appending to the output until the
    stack is empty.

这是我打印出错误结果的代码。

public class InfixToPostfix
{
    private static boolean isOperator(char c)
    {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'
                || c == '(' || c == ')';
    }

    private static boolean isLowerPrecedence(char op1, char op2)
    {
        switch (op1)
        {
            case '+':
            case '-':
                return !(op2 == '+' || op2 == '-');

            case '*':
            case '/':
                return op2 == '^' || op2 == '(';

            case '^':
                return op2 == '(';

            case '(':
                return true;

            default:
                return false;
        }
    }

    public static String convertToPostfix(String infix)
    {
        Stack<Character> stack = new Stack<Character>();
        StringBuffer postfix = new StringBuffer(infix.length());
        char c;

        for (int i = 0; i < infix.length(); i++)
        {
            c = infix.charAt(i);

            if (!isOperator(c))
            {
                postfix.append(c);
            }

            else
            {
                if (c == ')')
                {

                    while (!stack.isEmpty() && stack.peek() != '(')
                    {
                        postfix.append(stack.pop());
                    }
                    if (!stack.isEmpty())
                    {
                        stack.pop();
                    }
                }

                else
                {
                    if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
                    {
                        stack.push(c);
                    }
                    else
                    {
                        while (!stack.isEmpty() && isLowerPrecedence(c, stack.peek()))
                        {
                            Character pop = stack.pop();
                            if (pop != '(')
                            {
                                postfix.append(pop);
                            }
                        }
                    }

                    stack.push(c);
                }
            }
        }

        return postfix.toString();
    }

    public static void main(String[] args)
    {
        System.out.println(convertToPostfix("A*B-(C+D)+E"));
    }
}

程序应该打印 AB*CD+-E+ 但它正在打印 AB*-CD+E。 为什么输出不正确？

另外，这个问题有没有更优雅的解决方案。如果您有或知道，请分享。

Answer 1

问题出在你的其他部分:

               if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
                {
                    stack.push(c);
                }
                else
                {
                    while (!stack.isEmpty() && isLowerPrecedence(c, stack.peek()))
                    {
                        Character pop = stack.pop();
                        if (pop != '(')
                        {
                            postfix.append(pop);
                        }
                    }
                }

                stack.push(c);

所以在这里，当您看到堆栈不为空且优先级匹配更高时，您使用 stack.push() 将同一个 c 元素压入两次。

所以把这个 stack.push 放在 else 部分或者从 if 条件中移除 push。

另一个问题是，当最后堆栈中有一些运算符时，您不会将它们弹出。

这是我为您的案例编写的代码:

private static boolean isOperator(char c)
{
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'
            || c == '(' || c == ')';
}

private static boolean isLowerPrecedence(char op1, char op2)
{
    switch (op1)
    {
        case '+':
        case '-':
            return !(op2 == '+' || op2 == '-');

        case '*':
        case '/':
            return op2 == '^' || op2 == '(';

        case '^':
            return op2 == '(';

        case '(':
            return true;

        default:
            return false;
    }
}

public static String convertToPostfix(String infix)
{
    Stack<Character> stack = new Stack<Character>();
    StringBuffer postfix = new StringBuffer(infix.length());
    char c;

    for (int i = 0; i < infix.length(); i++)
    {
        c = infix.charAt(i);

        if (!isOperator(c))
        {
            postfix.append(c);
        }

        else
        {
            if (c == ')')
            {

                while (!stack.isEmpty() && stack.peek() != '(')
                {
                    postfix.append(stack.pop());
                }
                if (!stack.isEmpty())
                {
                    stack.pop();
                }
            }

            else
            {
                if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
                {
                    stack.push(c);
                }
                else
                {
                    while (!stack.isEmpty() && isLowerPrecedence(c, stack.peek()))
                    {
                        Character pop = stack.pop();
                        if (c != '(')
                        {
                            postfix.append(pop);
                        } else {
                          c = pop;
                        }
                    }
                    stack.push(c);
                }

            }
        }
    }
    while (!stack.isEmpty()) {
      postfix.append(stack.pop());
    }
    return postfix.toString();
}

public static void main(String[] args)
{
    System.out.println(convertToPostfix("A*B-(C+D)+E"));
}