使用 Stacks Java 中缀到 Postfix

2022-01-22 00:00:00 algorithm data-structures stack java

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

I am trying to write a program to convert an infix expression to a postfix expression.

我使用的算法如下:

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.

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

Here is my code which prints out wrong results.

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.为什么输出不正确?

The program should print AB*CD+-E+ but it is printing AB*-CD+E. Why is the output incorrect ?

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

Also, Is there a more elegant solution to this problem. Please share if you have or know one.

推荐答案

问题出在你的 else 部分:

Issue is with your else part:

               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 元素两次.

So here you are pushing the same c element twice with stack.push() when you see stack is not empty and precedence match is higher.

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

So put this stack.push within else part or remove the push from if condition.

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

Another issue is, when at the end you have some operators within the stack you dont pop them out.

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

Here's the code that i came up with for your case:

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"));
}

相关文章