基于数组的栈
function Stack(){
let items=[];
this.size=function()
{
return items.length;
}
//插入
this.push=function(e){
items.push(e);
}
//删除
this.pop=function(){
return items.pop();
}
//返回栈顶元素
this.peek=function(){
return items[items.length-1];
}
//判断栈是否为空
this.isEmpty=function(){
if(items.length===0)
{
console.log("栈为空");
}
else{
console.log("栈中有"+items.length+"个元素");
}
}
//清空栈
this.clear=function(){
items=[];
}
//打印栈内元素
this.print=function()
{
console.log(items.toString());
}
}
//测试
var stack=new Stack();
stack.push('1');
stack.print();// 1
stack.pop();//1
stack.isEmpty();//栈为空
栈的应用
十进制转二进制
function turn(num){
let result="";
var s=new Stack();
if(num===1){
return num;
}
while(num>=1)
{
s.push(Math.floor(num%2));
num=Math.floor(num/2);
}
while(s.size()>0)
{
result+=s.pop();
}
return result;
}
//测试
console.log(turn(8));// 1000
turn(1);//1
十进制转任意进制
function allturn(num,base)
{
let result="";
const stack=new Stack();
const remainder='0123456789ABCDEFGHIJKLMNOPQRSTOVWXYZ';
if(base<2||base>36)
{
return "";
}
while(num>0)
{
stack.push(Math.floor(num%base));
num=Math.floor(num/base);
}
while(stack.size()>0)
{
result+=remainder[stack.pop()];
}
return result;
}
//测试
allturn(8,2)//"1000"
allturn(35,8)//"43"
括号检验
括号检验中由于只需要删除而不需要返回栈顶元素,因此下面代码中的pop()函数中删去了return
function check(str)
{
const stack=new Stack();
for(var i=0;i<str.length;i++)
{
if(str[i]=='('||str[i]=='[')//判断左括号
{
stack.push(str[i]);
}
if(str[i]==')'||str[i]==']')//判断右括号
{
stack.pop();
}
}
if(stack.size()==0)
{
console.log('格式正确');
}
else
{
console.log('格式不正确');
}
}
//测试
var str='([])';
check(str)// 格式正确
undefined
var str='([([])])';
check(str)// 格式正确
undefined
var str='[[[][](((';
check(str)//格式不正确
undefined
var str='(2*4+(5-9)+[(2+3)*(7+7)])';
check(str)// 格式正确
行编辑程序
@表示删除前一个字符;#表示删除一整行
例如:you love he@@me = you love me
i love her#i love you = i love you
同样下面代码pop函数删除return
function check_line(str){
const stack=new Stack();
for(var i=0;i<str.length;i++)
{
switch(str[i])
{
case '@':
stack.pop();
break;
case '#':
stack.clear();
break;
default:
stack.push(str[i]);
break;
}
}
stack.print();
}
var str='you love he@@me';
check_line(str)// y,o,u, ,l,o,v,e, ,m,e
var str='i love her#i love you';
check_line(str)//i, ,l,o,v,e, ,y,o,u
计算表达式
函数judge:判断两个运算符的优先级(前一个和后一个比较)
function judge(a,b){
if(a=='+'&&(b=='+'||b=='*'||b=='/'||b=='('))
{
return '<';
}
else if(a=='-'&&(b=='-'||b=='*'||b=='/'||b=='('))
{
return '<';
}
else if(a=='*'&&(b=='*'||b=='('))
{
return '<';
}
else if(a=='/'&&(b=='/'||b=='('))
{
return '<';
}
else if(a=='('&&(b=='+'||b=='-'||b=='*'||b=='/'))
{
return '<';
}
else if((a=='('&&b==')')||(a=='#'&&b=='#'))
{
return '=';
}
else
{
return '>';
}
}
//测试
judge('+','+')//"<"
judge('(',')')//"="
judge('*','+')//">"
函数calculate:进行二元运算
function calculate(a,b,c)
{
if(c=='+')
{
return a+b;
}
else if(c=='-')
{
return a-b;
}
else if(c=='*')
{
return a*b;
}
else if(c=='/')
{
return a/b;
}
}
//测试
calculate(3,4,'+')//7
calculate(3,4,'/')//0.75
calculate(3,4,'*')//12
calculate(3,4,'-')//-1