【js数据结构】栈解决括号不匹配问题

时间:2024-11-14 21:37:43

栈可以用来判断一个算术表达式中的括号是否匹配。

思路:读取算术表达式,遇到左括号‘{’、‘[’、'('压入栈,栈的特点是后入先出,所以当遇到右括号‘}’、‘]’、')'的时候,取出栈顶元素,是否满足读取的右括号,栈顶是与之相匹配的左括号。最后判断栈是否为空,为空证明该表达式没有问题,否则则说明这个表达式存在括号不匹配问题。

首先我们构建一个栈。

function Stack(){
this.top = 0; //栈顶(属性)
this.arr = []; //用来存放栈的数组(属性)
this.push = push; //添加元素(方法)
this.pop = pop; //取出栈顶的元素 (方法)
this.peek = peek; //读取栈顶元素 (方法)
this.clear = clear; //清空栈 (方法)
this.len = len; //返回栈的长度 (方法)
this.isEmpty = isEmpty; //栈是否为空 (方法)
}

 函数实现:

function push(ele){
this.arr[this.top++] = ele;
}
function pop(){
return this.arr[--this.top];
} function peek(){
return this.arr[this.top-1];
} function clear(){
delete this.arr;
this.top = 0;
this.arr = [];
} function len(){
return this.top;
}
function isEmpty(){
if (this.len() <= 0)
return true;
else
return false;
}

  特别的,peek()与pop()函数不同在于,peek()只是读取栈顶,而不修改栈顶,而pop()是取出栈顶的元素,栈将压出栈顶元素。

  SignUp()函数接收两个参数,栈对象stack和读取的元素ele

function SignUp(stack, ele){

    switch (ele) {
case '{':
case '[':
case '(':
stack.push(ele);
break;
case '}':
case ']':
case ')':
topEle = stack.pop();
console.info(stack.top)
if(( topEle=='{'&&ele == '}')|| topEle=='('&&ele == ')'|| topEle=='['&&ele == ']') {
console.info('ok')
}
else{
console.info('括号不匹配');
return;
}
break;
}
}

  接下来就是new一个栈对象,读取表达式,然后一个一个调用SignUp函数了

input1 = document.getElementById('input1').value;
for(var i = 0; i<input1.length; i++)
{
SignUp(stack, input1[i]);
}
if (!stack.isEmpty())
console.info('括号不匹配');

  这里,我使用的是在html页面放置一个id叫input1的input标签,js获取其value后使其每一个字符都调用一次SignUp函数,最后判断栈内是否为空~

  代码又不完善之处还请各位大人多多提醒,小女子这厢有礼了>.<