首页 计算机科学 数据结构 栈

# 栈的应用

1. 括号匹配的检验

int pipei()
{ 
    sqstack s; char c; s.top=0; scanf(“%c”,&c);
	while(c!=’#’){
        switch(c){
            case ‘(‘ : push(s,c); scanf(“%c”,&c);break;
			case ‘{‘ : push(s,c); scanf(“%c”,&c);break;
			case ‘<‘ : push(s,c); scanf(“%c”,&c);break;
			case ‘)‘ : if(s.top==0) return -1; else if(*(s.top-1)==”(”) pop(s);
			scanf(“%c”,&c);break; else return -1;
			case ‘}‘ : if(s.top==0) return -1; else if(*(s.top-1)==”{”) pop(s);
			scanf(“%c”,&c);break; else return -1;
			case ‘>‘ : if(s.top==0) return -1; else if(*(s.top-1)==”<”) pop(s);
			scanf(“%c”,&c);break; else return -1;
           	}
    }
	if(s.top!=0) return -1;
	else return 0;
}

2. 表达式求值

为实现算法，使用两个工作栈。一个称做 OPTR, 用以寄存运算符；另一个称做 OPND, 用以寄存操作数或运算结果。算法的基本思想是:
(1) 首先置操作数栈为空栈，表达式起始符 “#” 为运算符栈的栈底元素；
(2) 依次读入表达式中每个字符，若是操作数则进 OPND 栈，若是运算符则和 OPTR 栈的栈顶运算符比较优先权，然后作相应操作，直至整个表达式求值完毕 (即 OPTR 栈的栈顶元素和当前读入的字符均为 “#”)。

OperandType EvaluateExpression(){
	// 算术表达式求值的算符优先算法。设 OPTR 和 OPND 分别为运算符栈和运算数栈
	//OP 为运算符集合 OPS 为运算符集合
	InitStack (OPTR);
    Push (OPTR,'#' );
	InitStack (OPND) ;
    C= getchar();
	while (c!='#' II GetTop(OPTR)!='#') {
		if (! In(C, 0P)) {
            Push((OPND, C); C = getchar(); 
        }else{// 不是运算符则进栈
			switch (Precede( GetTop(0PTR)，c)) {
				case '<': // 栈顶元素优先权低
					Push(OPTR, c); c = getchar(); break;
				case '=': // 脱括号并接收下一字符
					Pop(OPTR, x); c = getchar();break;
				case'>' : // 退栈并将运算结果入栈
					Pop(OPTR, theta);
					Pop(OPND, b); Pop(OPND, a);
					Push(OPND, Operate(a, theta, b)) ;break;
				}
            }
	}
	return GetTop( OPND) ;
} // EvaluateExpression
-->