Возникли проблемы с добавлением обработки скобок в мою реализацию маневровой станции

Я реализую алгоритм маневровой станции, и у меня возникают проблемы с обработкой скобок. Однако он отлично работает с несгруппированными выражениями. Вот что у меня есть без обнаружения скобок:

public void makePost(String e)
{
    String[] arr = e.split("");
    for(int i = 0; i < arr.length; i++)
    {
        if(arr[i].equals(" "))
        {
            continue;
        }
        Operator o = OperatorList.getOpMap().get(arr[i]);
        if(o == null){
            postfix += " " + arr[i];
            continue;
        }
        if(ops.isEmpty()){
            ops.push(o);
            continue;
        }
        else
        {

            while((!ops.isEmpty()  && (ops.peek().getPresedence() <= o.getPresedence()))){
                postfix += " " + ops.pop();
            }
            ops.push(o);
            continue;
        }

    }
    while(!ops.isEmpty())
    {
        postfix += " " + ops.pop();
    }
    postfix = postfix.trim();

}

ops — это стек, содержащий объекты Operator. Есть два типа операторов: функции (+,-,* и т. д.) и параны ("(","["). Как бы вы добавили к этому обработку скобок? Каждый раз, когда я пытаюсь, я не могу понять работать правильно

Вот что я пробовал:

    public void makePost(String e)
{
    String[] arr = e.split("");
    for(int i = 0; i < arr.length; i++){
        if(arr[i].equals(" ")){
            continue;
        }
        Operator o = OperatorList.getOpMap().get(arr[i]);
        if(o == null){
            postfix += " " + arr[i];
            continue;
        }
        if(ops.isEmpty()){
            ops.push(o);
            continue;
        }
        else
        {
            if(o.isParan())
            {
                Paran p = new Paran(o.toString());
                if(p.isOpen())
                {
                ops.push(o);
                System.out.println(ops);
                continue;
                }else{      
                    while(!ops.isEmpty()){ 
                        if(ops.peek().isParan()){
                            Paran n = new Paran(o.toString());
                            if(n.isOpen()){
                                ops.pop();
                                break;
                            }
                        }
                        postfix += " " + ops.pop();
                    }
                    continue;
                }
            }
            while((!ops.isEmpty()  && (ops.peek().getPresedence() <= o.getPresedence()))){
                postfix += " " + ops.pop();
            }
            ops.push(o);
            continue;
        }

    }
    while(!ops.isEmpty())
    {
        postfix += " " + ops.pop();
    }
    postfix = postfix.trim();

}

Я подозреваю, что состояние цикла while плохое, но я не знаю подходящей замены. Оно продолжается до бесконечности. Это была самая чистая реализация, которая у меня была. В основном то, что он должен делать, это когда он встречает открытую скобку, помещать ее в стек. Когда он попадает в закрытую, выталкивайте все из стека на выход, пока он не попадет в открытую скобку. Затем он должен сломаться и перейти к следующему токену.

if(o.isParan())
            {
                Paran p = new Paran(o.toString());
                if(p.isOpen())
                {
                ops.push(o);
                System.out.println(ops);
                continue;
                }else{      
                    while(!ops.isEmpty()){ 
                        if(ops.peek().isParan()){
                            Paran n = new Paran(o.toString());
                            if(n.isOpen()){
                                ops.pop();
                                break;
                            }
                        }
                        postfix += " " + ops.pop();
                    }
                    continue;
                }

РЕДАКТИРОВАТЬ: добавил мою попытку


person RN_    schedule 04.01.2014    source источник
comment
Это не домашнее задание, но я могу добавить свои попытки   -  person RN_    schedule 05.01.2014
comment
Я думаю, что это добавило бы доверия к вопросу, если бы вы показали, что что-то из того, что вы пробовали, не сработало - да, пожалуйста. Вы также можете ответить на множество других вопросов StackOverflow о Shunting Yard :). Прямо сейчас вверху списка справа от меня стоит вопрос о сохранении паренек в сортировочном дворе ;)   -  person GreenAsJade    schedule 05.01.2014
comment
Я обязательно проверю их :)   -  person RN_    schedule 05.01.2014
comment
не уверен, что вы уже видели это, но это может помочь: en.wikipedia.org/wiki /Shunting-yard_algorithm   -  person user2570465    schedule 05.01.2014
comment
Я использовал эту статью, чтобы написать это, но все равно спасибо :)   -  person RN_    schedule 05.01.2014
comment
Следующее, что я хотел бы сделать, это настроить цикл while. Черт возьми, пока вы это делаете, инструментируйте все это. Я подозреваю, что след того, что происходит, даст вам нужный ответ. Каждый раз, когда смотрите, распечатывайте, что такое ops.peek и ops.peek.getPrecedence. Каждый раз печатать постфикс. Должен быстро сказать вам, что происходит не так...   -  person GreenAsJade    schedule 05.01.2014
comment
есть ли конкретная причина, по которой у вас есть 2 типа скобок? я думаю, вы можете выполнить тот же порядок операций, используя только стандарт ( для всех ваших скобок, и это будет просто обработка скобок. (например, есть ли что-то 1-[(3+4)*5] может сделать это 1 -((3+4)*5) не может выполнить?   -  person user2570465    schedule 05.01.2014
comment
какая петля уходит в бесконечность? не похоже, что любой из ваших циклов может быть бесконечным. можете ли вы использовать операторы печати и подтвердить, какие циклы никогда не заканчиваются? (также вы используете свой собственный стек или встроенный стек Java?)   -  person user2570465    schedule 05.01.2014
comment
@user2570465 user2570465 первый цикл while(!ops.isEmpty()), тип скобки не имеет большого значения, нет. Я добавил это, если пользователь предпочел их. Я использую этот код для приложения, которое я делаю.   -  person RN_    schedule 05.01.2014
comment
какие операторы продолжают выполняться? оператор if или оператор postfix += " " + ops.pop()? или оба?   -  person user2570465    schedule 05.01.2014
comment
@ user2570465 Нет оператора, он продолжает работать, потому что стек заполнен и возвращает false для оператора if. Он никогда не доходит до оператора постфикса   -  person RN_    schedule 05.01.2014
comment
Вы еще не ответили на вопрос, почему бы вам просто не распечатать, что происходит в каждой точке?...   -  person GreenAsJade    schedule 05.01.2014
comment
@GreenAsJade Я потратил некоторое время на отладку операторов печати и нашел свою ошибку. Мой код выталкивает круглые скобки, потому что он имеет наивысший приоритет и находится на вершине стека. Я думаю, что либо добавлю новое условие в цикл while, либо использую какую-то рекурсию. Я попробую и посмотрю, что произойдет, и, надеюсь, смогу решить свою проблему.   -  person RN_    schedule 05.01.2014
comment
Это слово «приоритет», а не «присутствие».   -  person user207421    schedule 27.02.2017


Ответы (1)


Получил работу! Я добавил несколько проверок скобок в логических областях. Вот финал:

    public void makePost(String e)
{
    String[] arr = e.split("");
    for(int i = 0; i < arr.length; i++)
    {

        System.out.println(postfix + " " + i + " " + ops);
        if(arr[i].equals(" "))
        {
            continue;
        }
        if(arr[i].equals("(")){
            ops.push(new Paran("("));
            continue;
        }
        if(!ops.isEmpty() && arr[i].equals(")")){
            while(!ops.isEmpty() && !ops.peek().isOpen()){

                postfix += " " + ops.pop();
            }
            ops.pop();
        }
        Operator o = OperatorList.getOpMap().get(arr[i]);
        if(o == null){
            postfix += " " + arr[i];
            continue;
        }
        if(ops.isEmpty()){

            ops.push(o);

            continue;
        }
        else
        {

            while((!ops.isEmpty()  && (ops.peek().getPresedence() <= o.getPresedence()) && !(ops.peek() instanceof Paran))){

                postfix += " " + ops.pop();
            }
            ops.push(o);
            continue;

        }

    }

    while(!ops.isEmpty())
    {

        postfix += " " + ops.pop();
    }

   postfix = postfix.replaceAll("\\s[)]","");


}

У меня есть вызов replaceall(), потому что вывод продолжал возвращать закрывающую скобку вместе с правильным постфиксом, например:

2 4 * 7 8 4 * 4 4 5 * ) / ) * ) +

Я понятия не имею, почему это так, но я рад, что это работает

person RN_    schedule 05.01.2014
comment
Я предполагаю, что левые скобки оставлены, потому что OperatorList.getOpMap.get(() равно null. Просто предположение. Возможно, вы захотите проголосовать за некоторые комментарии, которые вам помогли;) GaJ - person GreenAsJade; 05.01.2014
comment
Это не ноль, я проверял. Я проголосовал за всех :) - person RN_; 05.01.2014
comment
Хм! Это точно похоже на причину :) - person GreenAsJade; 05.01.2014