java - 使用堆栈将Infix转换为Postfix

This question already has answers here:

Handling parenthesis while converting infix expressions to postfix expressions

（2个答案）


3年前关闭。





我必须制作一个程序，将以Infix表示法编写的表达式更改为Postfix表示法。我开始使用括号时遇到问题。例如，当我输入“ a +（c-h）/（b * d）”时，应显示为“ ac + h-b / d *”，而当它应显示为“ a c h-b d * / +”时。非常感谢您的帮助。谢谢。

import java.util.Scanner;
import java.util.Stack;

public class PostfixConverter {
    static private String expression;
    private Stack<Character> stack = new Stack<Character>();

    public PostfixConverter(String infixExpression) {
        expression = infixExpression;
    }

    public String infixToPostfix() {
        String postfixString = "";

        for (int index = 0; index < expression.length(); ++index) {
            char value = expression.charAt(index);
            if (value == '(') {

            } else if (value == ')') {
                Character oper = stack.peek();

                while (!(oper.equals('(')) && !(stack.isEmpty())) {
                    stack.pop();
                    postfixString += oper.charValue();

                }
            } else if (value == '+' || value == '-') {
                if (stack.isEmpty()) {
                    stack.push(value);
                } else {
                    Character oper = stack.peek();
                    while (!(stack.isEmpty() || oper.equals(('(')) || oper.equals((')')))) {
                        stack.pop();
                        postfixString += oper.charValue();
                    }
                    stack.push(value);
                }
            } else if (value == '*' || value == '/') {
                if (stack.isEmpty()) {
                    stack.push(value);
                } else {
                    Character oper = stack.peek();
                    while (!oper.equals(('+')) && !oper.equals(('-')) && !stack.isEmpty()) {
                        stack.pop();
                        postfixString += oper.charValue();
                    }
                    stack.push(value);
                }
            } else {
                postfixString += value;
            }
        }

        while (!stack.isEmpty()) {
            Character oper = stack.peek();
            if (!oper.equals(('('))) {
                stack.pop();
                postfixString += oper.charValue();
            }
        }
        return postfixString;
    }

    public static void main(String[] args) {
        System.out.println("Type an expression written in Infix notation: ");
        Scanner input = new Scanner(System.in);
        String expression = input.next();
        PostfixConverter convert = new PostfixConverter(expression);
        System.out.println("This expression writtien in Postfix notation is: \n" + convert.infixToPostfix());
    }
}

最佳答案

您提供的代码类似于this。但是该代码也不起作用。

我已经更新了您的代码和更改的added the comments。

import java.util.Scanner;
import java.util.Stack;

public class PostfixConverter {
    static private String expression;
    private Stack<Character> stack = new Stack<Character>();

    public PostfixConverter(String infixExpression) {
        expression = infixExpression;
    }

    public String infixToPostfix() {
        String postfixString = "";

        for (int index = 0; index < expression.length(); ++index) {
            char value = expression.charAt(index);
            if (value == '(') {
                stack.push('('); // Code Added
            } else if (value == ')') {
                Character oper = stack.peek();

                while (!(oper.equals('(')) && !(stack.isEmpty())) {
                    stack.pop();
                    postfixString += oper.charValue();
                    if (!stack.isEmpty()) // Code Added
                        oper = stack.peek(); // Code Added
                }
                stack.pop(); // Code Added
            } else if (value == '+' || value == '-') {
                if (stack.isEmpty()) {
                    stack.push(value);
                } else {
                    Character oper = stack.peek();
                    while (!(stack.isEmpty() || oper.equals(('(')) || oper.equals((')')))) {
                        oper = stack.pop(); // Code Updated
                        postfixString += oper.charValue();
                    }
                    stack.push(value);
                }
            } else if (value == '*' || value == '/') {
                if (stack.isEmpty()) {
                    stack.push(value);
                } else {
                    Character oper = stack.peek();
                    // while condition updated
                    while (!oper.equals(('(')) && !oper.equals(('+')) && !oper.equals(('-')) && !stack.isEmpty()) {
                        oper = stack.pop(); // Code Updated
                        postfixString += oper.charValue();
                    }
                    stack.push(value);
                }
            } else {
                postfixString += value;
            }
        }

        while (!stack.isEmpty()) {
            Character oper = stack.peek();
            if (!oper.equals(('('))) {
                stack.pop();
                postfixString += oper.charValue();
            }
        }
        return postfixString;
    }

    public static void main(String[] args) {
        System.out.println("Type an expression written in Infix notation: ");
        Scanner input = new Scanner(System.in);
        String expression = input.next();
        PostfixConverter convert = new PostfixConverter(expression);
        System.out.println("This expression writtien in Postfix notation is: \n" + convert.infixToPostfix());
    }
}