使用栈将中缀表达式转换为后缀表达式的Java代码

Question

使用栈将中缀表达式转换为后缀表达式的Java代码

4

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

我使用的算法如下：

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，为什么会出现错误？

此外，如果您有更优雅的解决方案，请分享一下。

- OneMoreError

调试它并亲自查看。 - SMA

我调试了它，但没找到问题，所以在这里发布了！ - OneMoreError

5个回答

2

我认为上面的答案不正确。

这是我纠正后的版本：

package Stack;

import java.util.Stack;

/*
 * 
Algorithm
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
…..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty), push it.
…..3.2 Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the precedence of the operator residing on the top of the stack. Push the scanned operator to the stack.
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘ is encountered.
6. Repeat steps 2-6 until infix expression is scanned.
7. Pop and output from the stack until it is not empty.

 */
public class InfixToPostFixEvalution {

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

    private static int getPrecedence(char ch) {
        switch (ch) {
        case '+':
        case '-':
            return 1;

        case '*':
        case '/':
            return 2;

        case '^':
            return 3;
        }
        return -1;
    }

    // A utility function to check if the given character is operand
    private static boolean isOperand(char ch) {
        return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
    }

    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 (isOperand(c)) {
                postfix.append(c);
            } else if (c == '(') {
                stack.push(c);
            }
            // If the scanned character is an ‘)’, pop and output from the stack
            // until an ‘(‘ is encountered.
            else if (c == ')') {

                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.append(stack.pop());
                }
                if (!stack.isEmpty() && stack.peek() != '(')
                    return null;
                else if(!stack.isEmpty())
                    stack.pop();
            }
            else if (isOperator(c)) // operator encountered
            {
                if (!stack.isEmpty() && getPrecedence(c) <= getPrecedence(stack.peek())) {
                    postfix.append(stack.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)^(f+g*h)-i"));
    }
}

- sam_k

0

我认为问题出在这里：

private static boolean isLowerPrecedence(char op1, char op2)
{
switch (op1)
{
    .....
    case '(':
        return true;
    .....
}

在情况下'(', 应该返回false。

- N.CY

在发布代码时，请考虑使用适当的缩进 - 这将使答案更易于阅读。 - CertainPerformance

0

这段代码将"("插入堆栈中，并相应地进行删除。这只是实现中缀转后缀的另一种方式。在这里，检查是直到我在堆栈中找不到较低优先级的运算符为止，我将弹出该值。例如，如果堆栈中有"-"，下一个运算符是"+"，它将弹出"-"，因为它具有相等的优先级。

我已经添加了自定义堆栈实现，但是Java提供的普通堆栈也可以替代使用。

import chapter4.LinkedListStack(custom stack implementation);

public class InfixToPostfix {

public String infixToPostfix(String str) {
    LinkedListStack<String> stack = new LinkedListStack<>();
    String[] st = str.split("");
    String result = "";
    for (String s : st) {
        if (operator(s)) {
            if (")".equals(s)) {
                while (!stack.isEmpty() && !"(".equals(stack.getTop())) {
                    result += stack.pop();
                }
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                if (!stack.isEmpty() && !isLowerPrecedence(s, stack.getTop())) {
                    stack.push(s);
                } else {
                    while (!stack.isEmpty() && isLowerPrecedence(s, stack.getTop())) {
                        String top = stack.pop();
                        if (!"(".equals(top)) {
                            result += top;
                        }
                    }
                    stack.push(s);
                }
            }
        } else {
            result += s;
        }
    }
    while (!stack.isEmpty()) {
        result += stack.pop();
    }

    return result;
}

private boolean isLowerPrecedence(String s, String s1) {
    switch (s) {
    case "+":
        return !("+".equals(s1) || "(".equals(s1));
    case "-":
        return !("-".equals(s1) || "(".equals(s1));

    case "*":
        return "/".equals(s1) || "^".equals(s1) || "(".equals(s1);
    case "/":
        return "*".equals(s1) || "^".equals(s1) || "(".equals(s1);

    case "^":
        return "(".equals(s1);

    case "(":
        return false;

    default:
        return false;
    }

}

private boolean operator(String s) {
    return "+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s) || "^".equals(s) || "(".equals(s) ||
            ")".equals(s);
}

public static void main(String[] args) {
    InfixToPostfix itp = new InfixToPostfix();
    System.out.println("The Postfix expression for A*B-(C+D)+E is: " + itp.infixToPostfix("A*B-(C+D)+E"));
    System.out.println("The Postfix expression for 1+2*4/5-7+3/6 is: " + itp.infixToPostfix("1+2*4/5-7+3/6"));
    System.out.println("The Postfix expression for a+(b*c)/d is: " + itp.infixToPostfix("a+(b*c)/d"));
}
}

public class LinkedListStack<E> {

private Node<E> head;

private static class Node<E> {
    E item;
    Node<E> next;

    public Node(E item, Node<E> next) {
        this.item = item;
        this.next = next;
    }
}

public void push(E item) {
    System.out.println("push: " + item);
    Node<E> newNode = new Node<>(item, null);
    newNode.next = head;
    head = newNode;
}

public E pop() {
    if (isEmpty()) {
        System.out.println("stack is Empty -> empty stack exception");
        return null;
    }
    System.out.println("pop: " + head.item);
    E data = head.item;
    head = head.next;
    return data;
}

public boolean isEmpty() {
    return head == null;
}

public E getTop() {
    return head.item;
}
}

- Krishna

0

这个解决方案需要在原始表达式周围放置适当的括号，但与我查看的其他答案相比，它非常简单和直接。只是为了那些可能需要它的人，因为这篇文章是一篇旧文章。

public static String InfixToPostfix(String origin) 
{

   String[] params = origin.split(" ");

   Stack<String> ops = new Stack<>();

   Stack<String> vals = new Stack<>();

 for (int i = 0; i < params.length; i++)
    {

switch (params[i]) {
    case "(":
        ;
        break;
    case "+":
        ops.push(params[i]);
        break;
    case "-":
        ops.push(params[i]);
        break;
    case "*":
        ops.push(params[i]);
        break;
    case "/":
        ops.push(params[i]);
        break;
    case "sqrt":
        ops.push(params[i]);
        break;
// Token not operator or paren: push double value.
       case ")":
            String d1 = vals.pop();
            String d2 = vals.pop();
            String op = ops.pop();
         vals.push("( " + d2 + " " + d1 + " "+ op + " )");
         break;
    default:
            vals.push(params[i]);
               break;    
        }
    }
   // System.out.print(vals.pop());
    return vals.pop();

      }

- OlaB

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SMA · Accepted Answer

问题出在您的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);

当您发现堆栈不为空且优先级匹配更高时，使用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"));
}