Сбалансированные круглые скобки

  

Указав строку выражения exp, напишите программу, чтобы проверить,   пар и порядков

"{","}","(",")","[","]"
     

верны в exp.

     

Например, программа должна печатать true для

exp = "[()]{}{[()()]()}"
     

и false для

exp = "[(])"

Сложность:

  • Сложность времени: \ $ O (n) \ $ где \ $ n \ $ - длина строки
  • Сложная сложность: \ $ O (\ frac {n} {2}) \ $ где \ $ n \ $ - длина строки

Я увидел версию Java и подумал: «Я хочу отправить версию JavaScript». Ищите обзор кода, оптимизацию и лучшие практики.

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

function parenthesesAreBalanced(s)
{
  var parentheses = "[]{}()",
    stack = [], //Parentheses stack
    i, //Index in the string
    c; //Character in the string

  for (i = 0; c = s[i++];)
  {
    var bracePosition = parentheses.indexOf(c),
      braceType;
    //~ is truthy for any number but -1
    if (!~bracePosition)
      continue;

    braceType = bracePosition % 2 ? 'closed' : 'open';

    if (braceType === 'closed')
    {
      //If there is no open parenthese at all, return false OR
      //if the opening parenthese does not match ( they should be neighbours )
      if (!stack.length || parentheses.indexOf(stack.pop()) != bracePosition - 1)
        return false;
    }
    else
    {
      stack.push(c);
    }
  }
  //If anything is left on the stack <- not balanced
  return !stack.length;
}

console.log('{}([]) true', parenthesesAreBalanced('{}([])'));
console.log('{{ false', parenthesesAreBalanced('{{'));
console.log('[(]) false', parenthesesAreBalanced('[(])'));
console.log("{}([]) true", parenthesesAreBalanced("{}([])"));
console.log("([}]) false", parenthesesAreBalanced("([}])"));
console.log("([]) true", parenthesesAreBalanced("([])"));
console.log("()[]{}[][]", parenthesesAreBalanced("()[]{}[][]"));
35 голосов | спросил konijn 2 AMpWed, 02 Apr 2014 03:05:26 +040005Wednesday 2014, 03:05:26

2 ответа


27

Это почти все предложения стиля; сам код выглядит великолепно.

Лично я предпочитаю стиль с фигурной скобкой для всех в JS, и я предпочитаю правильные блоки вместо наложения выражений. Но это только предпочтения. Я также пропустил побитовый трюк, добавил некоторые строгие сравнения вместо !stack.length и т. Д., Переместил i++ в свое «обычное» место и удлинил несколько имен переменных, просто для ясности.

Опять же: все это в принципе бессмысленно, но мне просто нравится написание вещей.

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

function parenthesesAreBalanced(string) {
  var parentheses = "[]{}()",
    stack = [],
    i, character, bracePosition;

  for(i = 0; character = string[i]; i++) {
    bracePosition = parentheses.indexOf(character);

    if(bracePosition === -1) {
      continue;
    }

    if(bracePosition % 2 === 0) {
      stack.push(bracePosition + 1); // push next expected brace position
    } else {
      if(stack.length === 0 || stack.pop() !== bracePosition) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

Обновление: на самом деле вы можете пропустить одну проверку stack.length во внутреннем условном выражении; stack.pop() просто вернет undefined, если пустой стек, поэтому этого достаточно:

if(stack.pop() !== bracePosition) {
  return false;
}
ответил Flambino 2 PMpWed, 02 Apr 2014 16:08:46 +040008Wednesday 2014, 16:08:46
4

Я написал библиотеку Node /JavaScript под названием сбалансированный , который может сделайте это и многое другое, но основной концепцией, которую я использовал, было использование стека, компиляция регулярного выражения тегов open /close, а затем выполнение 1 проход. Казалось, что он работает лучше, чем indexOf.

Как вы могли бы написать свой метод isBalanced, используя сбалансированный,

function isBalanced(string) {
    return !!balanced.matches({source: string, open: ['{', '(', '['], close: ['}', ')', ']'], balance: true});
}

Вот живой пример с исключениями: JSFiddle и вот пример игнорирование блоков комментариев JSFiddle

В вашем примере balanced будет выдана следующая ошибка

Balanced: mismatching close bracket, expected ")" but found "]" at 1:3

1: [(])
-----^
ответил Chad Scira 3 PM00000060000005231 2014, 18:35:52

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

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

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