Скобки и скобки Автозаполнение

Мне нужно выполнить последовательность фигурных скобок и скобок, например [ ], ( ), { } или отклонить ввод. Я могу добавить скобки /скобки только в начале или в конце.

Пример:

input: '))[[([{([])}' output: '(())[[([{([])}])]]'
input: '[)[((({}[]'   output: 'rejected'

Моя реализация основана на использовании стека (самообучающегося для улучшения из стандартного класса Stack на основе Vector), но, конечно, это можно сделать намного лучше.

public class BraceCompliter {
    private static final char L_PAREN    = '(';
    private static final char R_PAREN    = ')';
    private static final char L_BRACE    = '{';
    private static final char R_BRACE    = '}';
    private static final char L_BRACKET  = '[';
    private static final char R_BRACKET  = ']';
    private static StringBuilder currString;

public static void main(String[] args) {
    String test1 = "))[[([{([])}";
    String test2 = "[)[((({}[]";
    System.out.println(process(test1));
}


public static String process(String s) {
    currString = new StringBuilder(s);
    ArrayStack stack = new ArrayStack(s.length());
    int count = 0;
    for (int i = 0; i < s.length(); i++) {

        if      (s.charAt(i) == L_PAREN){
            stack.push(L_PAREN);
            count++;
        }
        else if (s.charAt(i) == L_BRACE)  {
            stack.push(L_BRACE);
            count++;
        }
        else if (s.charAt(i) == L_BRACKET) {
            stack.push(L_BRACKET);
            count ++;
        }
        else if (s.charAt(i) == R_PAREN) {
            if (stack.isEmpty())
                i = completeStart();
            else if (stack.pop() != L_PAREN)
                    return "rejected";
                else count--;
        }

        else if (s.charAt(i) == R_BRACE) {
            if (stack.isEmpty())
                i = completeStart();
            else if (stack.pop() != L_BRACE)
                return "rejected";
                else count--;
        }

        else if (s.charAt(i) == R_BRACKET) {
            if (stack.isEmpty())
                i = completeStart();
            else if (stack.pop() != L_BRACKET)
                return "rejected";
                else count--;
        }
    }
    if (!stack.isEmpty()) {
        completeEnd(stack, count);
    }
    return currString.toString();
}

private static void completeEnd(ArrayStack stack, int count) {
    for (int i = 0; i < count; i++) {
        Character ch = stack.pop();
        switch (ch) {
            case L_PAREN:
                currString.append(R_PAREN);
                break;
            case L_BRACE:
                currString.append(R_BRACE);
                break;
            case L_BRACKET:
                currString.append(R_BRACKET);
                break;
        }
    }
}

private static int completeStart() {
    int count = -1;
    for (int i = 0; i < currString.length(); i++) {
        char c = currString.charAt(i);
        if (c == L_BRACE || c == L_BRACKET || c == L_PAREN) {
            break;
        }
        switch (c) {
            case R_BRACE:
                currString.insert(0, L_BRACE);
                i++;
                count++;
                break;
            case R_BRACKET:
                currString.insert(0, L_BRACKET);
                i++;
                count++;
                break;
            case R_PAREN:
                currString.insert(0, L_PAREN);
                i++;
                count++;
                break;
        }
    }
    return count;
}

class ArrayStack {

    private int top;
    private char[] storage;

    ArrayStack(int capacity) {
        storage = new char[capacity];
        top = -1;
    }

    void push(char value) {
        top++;
        storage[top] = value;
    }

    char pop() {
        return storage[top--];
    }

    boolean isEmpty() {
        return (top == -1);
    }
}
}

Все отзывы приветствуются.

11 голосов | спросил user2929711 19 SatEurope/Moscow2015-12-19T00:36:59+03:00Europe/Moscow12bEurope/MoscowSat, 19 Dec 2015 00:36:59 +0300 2015, 00:36:59

3 ответа


7

Не повторяйте себя

Повторения в операторе switch требуют рефакторинга в управляемый данными код. По существу, объявите openers и closers как

    public static string openers = "([{";
    public static string closers = ")]}";

Теперь цикл в методе process сжимается до

        for (...) {
            char ch = s.charAt(i);
            int index;
            if ((index = openers.indexOf(ch)) != -1) {
                stack.push(ch);
                count++;
            } else {
                index = closers.indexOf(ch);
                assert(index != -1);
                if (stack.isEmpty()) {
                    i = completeStart()
                } else {
                    opener = stack.pop();
                    if (openers.indexOf(opener) != index)
                        return "rejected"
                    count--;
                }
            }
        }

и completeStart должны следовать примеру.

На стороне примечания, я не уверен, что мне нравится completeStart цикл по исходной строке. Я рекомендую реорганизовать его, чтобы завершить только один открыватель за раз.

ответил vnp 19 SatEurope/Moscow2015-12-19T02:09:07+03:00Europe/Moscow12bEurope/MoscowSat, 19 Dec 2015 02:09:07 +0300 2015, 02:09:07
7

Извлечь общий код в каждой условной ветви

В блоке:

    switch (c) {
        case R_BRACE:
            currString.insert(0, L_BRACE);
            i++;
            count++;
            break;
        case R_BRACKET:
            currString.insert(0, L_BRACKET);
            i++;
            count++;
            break;
        case R_PAREN:
            currString.insert(0, L_PAREN);
            i++;
            count++;
            break;
    }

Вы всегда выполняете:

        i++;
        count++;

Таким образом, вы можете просто упростить и написать:

    switch (c) {
        case R_BRACE:
            currString.insert(0, L_BRACE);
            break;
        case R_BRACKET:
            currString.insert(0, L_BRACKET);
            break;
        case R_PAREN:
            currString.insert(0, L_PAREN);
            break;
    }
    i++;
    count++;
ответил Caridorc 19 SatEurope/Moscow2015-12-19T01:18:26+03:00Europe/Moscow12bEurope/MoscowSat, 19 Dec 2015 01:18:26 +0300 2015, 01:18:26
2

Класс ArrayStack:

class ArrayStack {

    private int top;
    private char[] storage;

    ArrayStack(int capacity) {
        storage = new char[capacity];
        top = -1;
    }

    void push(char value) {
        top++;
        storage[top] = value;
    }

    char pop() {
        return storage[top--];
    }

    boolean isEmpty() {
        return (top == -1);
    }
}

Хорошо написано. Некоторые моменты:

  1. Сделайте его общим, чтобы его можно было использовать позже.
  2. Сделать общедоступным, чтобы его можно было использовать позже.
  3. Ваш метод pop() будет вызывать ArrayIndexOutOfBoundsException, если стек пуст. Если вы намеревались это, ну, ладно, но я бы просто вернулся null.
  4. Поскольку вы получаете только верхнюю часть стека (как предполагается, должны быть стеки), вы должны реализовать стек, который может изменить его размер, но при этом иметь схожую эффективность. Как бы вы это сделали? Ну:

    • Как и LinkedList, вы можете иметь Node s, указывающий ниже:

      class Node {
      
          private Node below;
          private T value;
      
          Node(Node below, T value) {
              this.below = below;
              this.value = value;
          }
      
      }
      
    • Класс будет содержать верхний Node:

      public class Stack<T> {
      
          private Node top;
      
          // ...
      
      }
      
    • Напишите конструктор:

      public Stack() {
          this.top = null;
      }
      
    • Затем реализуем методы:

      public void push(T value) {
          this.top = new Node(this.top, value);
      }
      
      public T pop() {
          if (top == null) {
              return null;
          }
          T result = top.value;
          top = top.below;
          return result;
      }
      
      public boolean isEmpty() {
          return top == null;
      }
      
    • Теперь составьте это:

      public class Stack<T> {
      
          private Node top;
      
          public Stack() {
              this.top = null;
          }
      
          public void push(T value) {
              this.top = new Node(this.top, value);
          }
      
          public T pop() {
              if (top == null) {
                  return null;
              }
              T result = top.value;
              top = top.below;
              return result;
          }
      
          public boolean isEmpty() {
              return top == null;
          }
      
          class Node {
      
              private Node below;
              private T value;
      
              Node(Node below, T value) {
                  this.below = below;
                  this.value = value;
              }
      
          }
      
      }
      
ответил TheCoffeeCup 20 SunEurope/Moscow2015-12-20T02:36:31+03:00Europe/Moscow12bEurope/MoscowSun, 20 Dec 2015 02:36:31 +0300 2015, 02:36:31

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132