Баланс открывающихся и закрывающихся скобок.Стеки в JS
Помогите пожалуйста с программой на JavaScript((((((((
Задание: Проверка баланса открывающихся и закрывающихся скобок через стек. Т.е. 1)Пустая строка допустима; 2)Если () и [] допустимо, то ()[] допустимо; 3)Если () допустимо, то (){}[] допустимо; )(-нет ({)}-нет Нашла множество реализаций данной задачи на других языках, но на JS нет, сама перевести не могу, пожалуйста помогите. |
Обычно стратегия "от центра";
"от центра"; 1. Ищется последняя открывающаяся скобка 2. От текущего местоположения ищется первая закрывающаяся скобка, контент вместе с найденными скобками изымается и помещается в стек. 3. Проверка наличия открывающихся скобок, если да - переход на цифру 1 |
Lesya,
На самом деле, все не так сложно. :) Чтобы проще отслеживать соответствие произвольного символа той или иной скобочной паре, создадим ассоциативный массив (хеш) на основе самих скобочных символов. Значением ключа сделаем объект, содержащий условный идентификатор скобочной пары и флаг, определяющий скобку как открывающую или закрывающую. Стеком пусть будет обычный массив. По мере чтения символов будем смотреть в хеш, и если текущий символ там есть, то: - если скобка открывающая, добавляем в стек идентификатор; - если закрывающая, сравним ее идентификатор с последним значением в стеке, и если идентификаторы не равны или стек уже пуст, значит в строке ошибка, если нет, снимаем шапку стека и продолжаем; К концу строки, если все скобки закрыты, то и стек будет пуст.
<body>
<input id="string" type="text" size="30"><br><br>
<input id="testme" type="button" value="Test me!"><br><br>
<span id="result"></span>
<script>
function bracketTester ( brackets ) {
if ( typeof brackets != "string" ) {
throw new Error( "'brackets' is not a string" );
}
if ( brackets.length % 2 ) {
throw new Error( "'brackets' length is not even" );
}
var table = {};
var bracket, i;
for ( i = 0; i < brackets.length; i++ ) {
if ( table.hasOwnProperty( bracket = brackets.charAt( i ) ) ) {
throw new Error( "non-unique character encountered" );
}
table[ bracket ] = {
id : i >>> 1,
open : !( i % 2 )
};
}
return function ( string ) {
if ( typeof string != "string" ) {
throw new Error( "'string' is not a string" );
}
var stack = [];
var bracket, i;
for ( i = 0; i < string.length; i++ ) {
if ( table.hasOwnProperty( bracket = string.charAt( i ) ) ) {
if ( table[ bracket ].open ) {
stack.push( table[ bracket ].id );
}
else if ( stack.length == 0 || stack.pop() != table[ bracket ].id ) {
return false;
}
}
}
return stack.length == 0;
}
}
var test = bracketTester( "()[]{}<>" );
function byId ( id ) {
return document.getElementById( id );
}
byId( "string" ).value = "<><(([]){}<[{{{{}}[[]]}}]>)>";
byId( "testme" ).onclick = function () {
byId( "result" ).innerHTML = test( byId( "string" ).value ) ? "Valid" : "Invalid";
}
</script>
</body>
|
Вариант для (){}[]
function balance(a) {
for (var d = /(\u005B|\u0028|\u007B)[^\u005B\u0028\u007B]*?$/,
e = {
"(": /\u0028[^\u007D\u005D]*?\u0029/,
"[": /\u005B[^\u0029\u007D]*?\u005D/,
"{": /\u007B[^\u0029\u005D]*?\u007D/
}, b, c = !0; c;) b = a, a = a.replace(d, function (a, b) {
return a.replace(e[b], "")
}), b == a && (c = !1);
return !/[\u005B\u005D\u0028\u0029\u007B\u007D]/.test(a)
};
alert(balance("{}({}123(45))")+"\n"+balance("{}{}1234][5")+"\n"+balance("<><(([]){}<[{{{{}}[[]]}}]>)>"))
|
рони,
Да ну, препод не поверит же.) |
Спасибо большое
уже сдала)))спасибо
|
теперь нужно преобразовать программу
Разбор числового выражения например: (((1+2)+3)*10-(3-1))/10= Если расстановка скобок верна, то выводить ответ, если нет-"ошибка" Решить через рекурсию. Подскажите как? |
var arr=[
'(((1+2)+3)*10-(3-1)))/10=',
'(((1+2)+3)*10-(3-1))/10=',
'(((1+)2)+3)*10-(3-1))/10=',
'(((1+2()+3)*10-(3-1))/10='
]
function rep (a){
var c=a;
var b=true;
while (a.search(/[\(\)]/g)!= -1&&b) {
a = a.replace(/\([^\(\)]+\)/g,'$');//alert(a)
b = a.split(/\(|\)/).length!=2 && a.replace(/\(\)/g,'')==a;
}
if(b){b=eval(c.replace("=",""))}
return b;
}
for(var i in arr){
alert('N='+i+'\n'+arr[i]+' ' +rep (arr[i]+';'));
}
|
Lesya,
Вариант...
function balance(a) {
var b;
b = a;
a = a.replace(/(\u0028)[^\u0028]*?$/, function (a) {
return a = a.replace(/\u0028(.*?)\u0029/, function (a) {
return eval(a)
})
});
b != a && (a = balance(a));
return !/[\u0028\u0029]/.test(a) ? eval(a) : !1
};
alert(balance("(((1+2)+3)*10-(3-1))/10")+"\n"+balance("(((1+2)+3)*10)-(3-1))/10"))
|
необходимо создать поле для ввода уравнения, т.е. уравнение не конкретно это, а вводим сами любое
|
| Часовой пояс GMT +3, время: 11:36. |