Стек. Алгоритм проверки правильности расстановки скобок разных типов.
Алгоритм проверки правильности расстановки скобок разных типов.
Алгоритм проверки правильности расстановки скобок разных типов.
А какие проблемы? Встретилась в тексте открывающая скобка типа "1" - добавляем в стек 1. Встретилась типа "2" - добавляем 2. И т. д. Теперь о закрывающих. Встретилась закрывающая типа "2" - проверяем вершину стека. Если там 2, сбрасываем и продолжаем анализ. Если не 2 или пустой стек - сообщение об ошибке (вида: на таком-то месте исходного текста нет закрывающей скобки вида.. . Вид - в вершине стека) . И так до конца текста. Если после окончания текста стек пустой - все ОК. Иначе, сообщение об ошибке: "Не хватает закрывающей скобки типа (вывести значение из вершины стека).
мм, вот писал когда то ...
это javascript:
var names=[];
names[1] = '4((( (a+[b*c]-{d/3}[f]))))';
names[0]='((((a + [b() * c) - 17])))';
names[2]='(((a * x) + [b] * y)';
names[3]='+ c auf(zlo)men [gy] four{s}';
var ret;
var open={ // Открывающие и закрывающие скобки размещаем в ассоциативном массиве,
// открывающие как ключи, а закрывающие как значения
'(':')',
'{':'}',
'[':']',
'<':'>',
};
var close={};
for (key in open){ close[open[key]]=key;} // меняе местами ключи и значения для поиска закрывающих скобок
var pushpop=[]; // массив для стека
names.forEach(function(item, j, names) { // перебираем входные значения names
var lett = item.split(''); // делим строчку на знаки
var string=""; // чистим строку и массив
pushpop=[];
for (var i = 0; i < lett.length; i++) { // перебор по буквам
ret=0;
if(!check_open(lett[i])){ // если буква не в открывающих
if(!check_close(lett[i])&&ret==1) { // то она может быть в закрывающих
// но если закрывает неверно тогда пишем
alert("Ошибка в:" +item+" " + string + "I" + lett[i]+ "I");
document.write("Ошибка в:" +item+" " + string + "I" + lett[i]+ "I
");
break;
};
};
string=string+lett[i];
};
if (pushpop.length>0&&ret!=1) {
alert("Ошибка в:" +item+" I не закрыты: " + pushpop.join()+ "I");
document.write("Ошибка в:" +item+" I не закрыты: " + pushpop.join()+ "I
");
//code
}else if(ret!=1){
document.write(item + ' ok
')
};
});
function check_open(args) {
if (typeof open[args] != "undefined") { // проверяем есть ли среди открывающих символов
pushpop.push(args); // если есть добавляем в массив открытых
return true;
};
return false;
};
function check_close(args) {
var i;
if (typeof close[args]!="undefined") { // если в массиве закрывающих элементов то
i=pushpop.length-1;//смотрим что собой представяем последняя открытая скобка
if(open[pushpop[i]]==args){ // если закрывающая скобка соответствует последней открывающей то
var remd= pushpop.pop(); //закрываем скобку
return true;
}else{
// Если скобка закрывающая но неправильная
ret=1;
return false;
};
};
};