Инфикс Java RPN (обратная польская запись) к постфиксу

Question

Я почти уверен, что стеки используются для построения PRN, а '(' игнорируются, но, похоже, это не так. Например:

• вход 1: 52+ (1 + 2) * 4-3
• вход 2: 52 + ((1 + 2) * 4) -3
• вход 3: (52 + 1 + 2) * 4-3

Вход 1 и выход 2 должны быть одинаковыми, а вход 1 и вход 3 должны отличаться.

• выход 1: 52 1 2 + 4 3 - * +
• выход 2: 52 1 2 + 4 * 3 - +
• выход 3: 52 1 2 + 4 3 - * +

    public static String Infix2(String input) {
        char[] in = input.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        StringBuilder out = new StringBuilder();

        for (int i = 0; i < in.length; i++)
            switch (in[i]) {
            case '+':
            case '*':
            case '-':
                out.append(' ');
                stack.push(in[i]);
                break;
            case ' ':
            case '(':
                break;
            case ')':
                out.append(' ');
                out.append(stack.pop());
                break;
            default:
                out.append(in[i]);
                break;
            }

        while (!stack.isEmpty()) {
            out.append(' ');
            out.append(stack.pop());
        }

        return out.toString();
    }

Предполагая, что я хочу, чтобы вход 1 и 3 также работал, какой подход я должен использовать?

редактирование: После того, как изменения «+», «-», «*» и «/» сработали для заданных входов.

public static String Infix2(String input) {
    if (input == null)
        return "";
    char[] in = input.toCharArray();
    Stack<Character> stack = new Stack<Character>();
    StringBuilder out = new StringBuilder();

    for (int i = 0; i < in.length; i++)
        switch (in[i]) {
        case '+':
        case '-':
            while (!stack.empty()
                    && (stack.peek() == '*' || stack.peek() == '/'))
                out.append(' ').append(stack.pop());
        case '*':
        case '/':
            out.append(' ');
        case '(':
            stack.push(in[i]);
        case ' ':
            break;
        case ')':
            while (!stack.empty() && stack.peek() != '(')
                out.append(' ').append(stack.pop());
            if (!stack.empty())
                stack.pop();
            break;
        default:
            out.append(in[i]);
            break;
        }

    while (!stack.isEmpty())
        out.append(' ').append(stack.pop());

    return out.toString();
}

Answer 1

Алгоритм довольно прост (и вот хорошее объяснение ). Каждая операция имеет вес привязки, где + и - наименьший. Есть два правила:

• распечатывать номера сразу
• никогда не кладите более легкий предмет на более тяжелый предмет
• левые скобки идут в стек
• правые скобки выскакивают из стека, пока вы не нажмете левую скобку, а затем удалите левые скобки

Учитывая ваш первый пример, 52+ (1 + 2) * 4-3, вот стек:

 52+          => +
 52+(         => + (
 52+(1+       => + ( + 
 52+(1+2)     => +       //right parentheses popped +
 52+(1+2)*4   => + * 
 52+(1+2)*4-3 => + -     //can't put - on top of *, so pop off *
 ... and then pop the stack until it's empty.

Замена вашей петли переключателя на следующую (ближайший аналог того, что вы имели) даст правильные ответы для ваших трех примеров. В реальном парсере вы бы дали каждому оператору вес и обобщили бы поп-механизм.

for (int i = 0; i < in.length; i++)
        switch (in[i]) {
        case '+':
        case '-':
            while (!stack.empty() && (stack.peek() == '*' || stack.peek() == '/')) {
                out.append(' ');
                out.append(stack.pop());
            }
            out.append(' ');
            stack.push(in[i]);
            break;
        case '*':
        case '/':
            out.append(' ');
            stack.push(in[i]);
            break;
        case '(':
            stack.push(in[i]);
            break;
        case ')':
            while (!stack.empty() && stack.peek() != '(') {
                out.append(' ');
                out.append(stack.pop());
            }
            stack.pop();
            break;
        default:
            out.append(in[i]);
            break;
        }

Answer 2

Не точный ответ на конкретный вопрос, но что-то, что я бы порекомендовал для разработки алгоритмов такого типа: взгляните на тестовое развитие (TDD). Вкратце: напишите несколько модульных тестов - например, с помощью JUnit - для метода infix2, где вы кормите метод тестовыми шаблонами (выражениями) и test, если infix2 выдает правильный вывод.

Начните с простых, как

assertequals("1", "1"); // positive number
assertequals("-1", "-1"); // negative number
assertequals("1+1", "1 1 +"); // simple addition
assertequals(" 1 + 1 ", "1 1 +"); // simple addition with whitechars
assertequals(" 1 + +1 ", "1 -1 +"); // simple addition with pos. number & whitechars
assertequals(" 1 + -1 ", "1 -1 +"); // simple addition with neg. number & whitechars
assertequals("(1+1)", "1 1 +"); // simple addition with brackets

и не забывайте недопустимые выражения типа

String[] illegalExpressions = {null, "", " ", "1 +", "1 + 1)"};

Примеры тестов для вас должны быть

assertequals("52+(1+2)*4-3", "52 1 2 + 4 * 3 -");
assertequals("52+((1+2)*4)-3", "52 1 2 + 4 * 3 -");
assertequals("(52+1+2)*4-3", "52 1 + 2 + 4 * 3 -");