Сравнивая две разные пары типов данных?

Question

Я работаю над проблемой, чтобы проверить, сбалансирован ли парантез в Java.

Каждый парантез имеет тип, а тип - это случайное целое число.

(0 (1) 1 (2 (0) 0) 2) 0

^ это будет считаться сбалансированным.

Я использую стек для реализации этого, но я не понимаю, как бы я сравнил и / или спарил значения для их сравнения?

Это то, что у меня сейчас на месте.

public class Parenthesis
{
private static final char OPEN = '(';
private static final char CLOSE = ')';

public static boolean isPair(char char1, char char2, int num1, int num2)
{
    if(char1 == OPEN && char2 == CLOSE && num1 == num2)
    {
        return true;
    }
    return false;
}

public static boolean checkBalanced(int[] p, boolean[] b)
{
    Stack storage = new Stack(b.length);

    for(int i=0; i<p.length; i++)
    {
        if(b[i]==false)
        {
           char o=OPEN;
           int numO=p[i];
           storage.push(o, numO);
        }
        else if(b[i]==true)
        {
            char c=CLOSE;
            int numC=p[i];
            if (storage.isEmpty() || 
!isPair(storage.popSymb(),c,storage.popNum(),numC))
            {
                return false;
            }
        }
    }
    if(storage.isEmpty())
    {
        return true;
    }
    else
        {
            return false;
        }
}
}

Answer 1

Может быть, этот код может помочь вам:

import java.util.Stack;

import java.util.Stack;

public class Parenthesis {

    private static class Pair {

        private final char parenthesis;
        private final char number;

        Pair(String value) {
            this.parenthesis = value.charAt(0);
            this.number = value.charAt(1);
        }

        boolean canFormAPairWith(Pair pair) {
            if (parenthesis == ')') {
                return false;
            }
            return this.number == pair.number && pair.parenthesis == ')';
        }

    }

    public static void main(String[] args) {

        Stack<Pair> stack = new Stack<>();

        String example = "(0(1)1(2(0)0)2)0";
        for (String s : example.split("(?<=\\G.{2})")) {

            Pair currentPair = new Pair(s);
            if (!stack.isEmpty() && stack.peek().canFormAPairWith(currentPair)) {
                stack.pop();
            } else {
                stack.push(currentPair);
            }
        }

        System.out.println(stack.isEmpty());

    }
}

Я не проверял во всех случаях, но для вашего случая работает.

Answer 2

ТЛ; др

Для этого есть инструмент!

Нет необходимости писать код Java. Просто используйте ANTLR с грамматикой, приведенной ниже.

Да, ваш ввод (0(1)1(2(0)0)2)0 проходит как сбалансированный.

ANTLR 4

ANTLR - инструмент распознавания языка.

• Этап 1
  Вы передаете ANTLR файл «грамматики», определяющий язык программирования (Java, C, COBOL и т. Д.) Или структуру данных (XML, JSON, CSV и т. Д.), и ANTLR генерирует исходный код Java для лексера и анализатора.
• Фаза 2
  Вы компилируете эти источники. Затем запустите эти классы, предоставив исходный код или файл данных для анализа.
  • Lexing
    Поток символов обрабатывается для идентификации слов, ранее известных как tokens .
  • Синтаксический анализ
    Поток токенов обрабатывается для идентификации предложений (операторов на языке программирования или строк в файле данных). В результате получается Абстрактное синтаксическое дерево .

Используйте класс TestRig в комплекте с ANTLR 4 для ввода значения с помощью консоли или файла. Если ваша входная строка чисел и паренов не сбалансирована должным образом, синтаксический анализ lexing будет сигнализировать об ошибке.

Я новичок в ANTLR, но эту грамматику я адаптировал из примера в Справочник по ANTLR 4 от Terence Parr (создатель проекта ANTLR ), похоже, делает эту работу за вас.

grammar ParenBalance;

prog:   stat+ ;

stat:   expr NEWLINE
    |   NEWLINE
    ;

expr:  expr expr
    |   INT
    |   '(' expr ')'
    ;

INT :   [0-9]+ ;         // match integers
NEWLINE:'\r'? '\n' ;     // return newlines to parser (is end-statement signal)
WS  :   [ \t]+  ;

Попробуйте некоторые входные данные (все с Newline , не показан):

• 42 проходит
• (42) проходит
• (42 терпит неудачу, отсутствует ')'
• 42) не удалось, посторонний ввод ')'
• (((1)2)3) проходит
• ((1 2)3) Сбой, несоответствующий вход '', посторонний вход ')'

Давайте попробуем ваш ввод.

• (0(1)1(2(0)0)2)0 проходит.

Вот скриншот ANTLR 4 в действии через плагин ANTLR4 для IntelliJ IDE. Нажмите, чтобы увеличить. ANTLR фактически управляется либо консолью, либо кодом Java. Плагин, показанный здесь, обрабатывает это взаимодействие от нашего имени, поэтому мы можем удобно работать в IDE.

Answer 3

Если вы хотите реализовать этот алгоритм вручную, вам нужно выполнить несколько шагов:

1. Если символ является открытой скобкой, вставьте его в стек.
2. Если символ является закрытой скобкой:
   • Если стек не пустой и последний символ в стеке - открытая скобка, просто откройте открывающую скобку.
   • Иначе вставьте закрытую скобку в стек.
3. Если в результате стек будет пустым, ваше выражение будет сбалансированным.

Например:

public class Parenthesis {
private static final char OPEN = '(';
private static final char CLOSE = ')';

private static boolean checkBalanced(String str) {

    Stack<Character> storage = new Stack<>();

    char[] chars = str.toCharArray();
    for (char ch : chars) {
        if (ch == OPEN) {
            storage.push(ch);
        }

        if (ch == CLOSE) {
            if (storage.size() != 0 && storage.peek() == OPEN) {
                storage.pop();
            } else {
                storage.push(ch);
            }
        }
    }

    return storage.size() == 0;
}

public static void main(String[] args) {
    System.out.println(checkBalanced("(0(1)1(2(3)2)2)0"));
}

Но я советую вам использовать обратную польскую запись для реализации этого алгоритма.https://en.wikipedia.org/wiki/Reverse_Polish_notation http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm