Проверьте, является ли строка синтаксически верной

Я пытаюсь решить задачу с помощью регулярного выражения. Дана функция со строковым параметром. Строка содержит фигурные скобки (){}<>[]. Я должен проверить, является ли строка синтаксически верной, и я также должен подсчитать количество вложенных фигурных скобок. Это моя версия (неполная) `

const checkBraces = (str) => {
  const newStr = str.replace(/[^(){}<>[\]]+/gi, '');
  let answer = newStr.match(/\(+\)+|\<+\>+|\{+\}+|\[+\]+/g);
  console.log(answer);
}

и это минимальное количество тестов для функции `

checkBraces("---(++++)----") == 0
checkBraces("") == 0
checkBraces("before ( middle []) after ") == 0
checkBraces(") (") == 1
checkBraces("} {") == 1
checkBraces("<(   >)") == 1
checkBraces("(  [  <>  ()  ]  <>  )") == 0
checkBraces("   (      [)") == 1

Если есть ошибка en, функция должна вернуть 1, иначе 0. В своей функции я сначала попытался заменить все non-braces, поэтому у меня есть четкая строка. Теперь я не могу решить эту проблему.

Вам нужно использовать регулярные выражения?

Sean Bright 13.09.2018 20:42

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

zfrisch 13.09.2018 20:43

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

Norayr Ghukasyan 13.09.2018 20:47
I am trying to solve a task with RegEx Есть конкретная причина, по которой вы хотите это сделать? Готовы ли вы использовать лучшие альтернативы? Регулярное выражение - это возможный, но оно будет, по крайней мере, некрасивым, и его будет довольно сложно поддерживать.
VLAZ 13.09.2018 20:47

нет, я могу использовать другие решения, просто я подумал, что регулярное выражение - лучшее решение.

Norayr Ghukasyan 13.09.2018 20:49

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

epascarello 13.09.2018 20:49

Я не смог найти подобный вопрос.

Norayr Ghukasyan 13.09.2018 20:50
but i think only with regex i can solve it как раз наоборот - регулярное выражение, вероятно, является одним из худших инструментов для решения этой проблемы. Если вы просто хотите сопоставить фигурные скобки, это достаточно просто сделать с помощью стека - пройти по строке символ за символом, добавить открывающие фигурные скобки в стек по мере их появления, а затем удалить их, когда вы найдете подходящую закрывающую скобку. Фактически, вы можете свести его к простому счетчику и просто оставить несколько из них для каждого типа скоб.
VLAZ 13.09.2018 20:50

Случаев таких "(<)>" не раз бывает. В этом случае ваша версия не работает

Norayr Ghukasyan 13.09.2018 20:56

Извините, вы правы - счетчики не работают. Но стек все еще есть. Если вы встретили закрывающую скобку, а верхняя часть стека НЕ ​​совпадает, значит, у вас неправильное расположение скобок.

VLAZ 13.09.2018 21:00
1
10
78
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

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

let braces = { // lookup to match closing with opening
    '(':')',
    '{':'}',
    '<':'>',
    '[':']'
}
let closing = new Set([')', '}', '>', ']']) // quick lookup of brackets
let opening = new Set(['(', '{', '<', '['])

function checkBraces(str) {
    /* returns true if balanced, false if unbalanced */
    let stack = []
    for (l of str){
        if (closing.has(l)){                            // found a closing bracket
            if (l !== braces[stack.pop()]) return false // does it match the last opening?
        } else if(opening.has(l)) stack.push(l)         // found an opening push to the stack
    }
    return stack.length === 0 
}
console.log(checkBraces("before ( middle []) after "))
console.log(checkBraces("<(   >)"))
console.log(checkBraces("(  [  <>  ()  ]  <>  )"))
console.log(checkBraces("   (      [)"))
console.log(checkBraces(" )"))
console.log(checkBraces(" <"))

Отличное решение. Большое спасибо

Norayr Ghukasyan 13.09.2018 21:36

Не использует никаких встроенных функций, кроме push и pop.

function check(s) {
  var arr = [];

  for (let i = 0; i < s.length; i++) {
    if (s[i] === '{' || s[i] === '[' || s[i] === '(' || s[i] === '<' ) {
        arr.push(s[i]);
    } else if (s[i] === '}' || s[i] === ']' || s[i] === ')' || s[i] === '>' ) {
        if ( arr[arr.length-1] === s[i] ) {
            arr.pop();
        } else {
            return 'not balanced';
        }
    }
  }
  if(arr.length) return 'not balanced';
  return 'balanced';
}

console.log(check('{781234}[3,4,5,6         ]<       >( sdfhniusdf  )'));
console.log(check('asssssssssss {}');
console.log(check(' as<  habsdj');

Другие вопросы по теме