1.     括号匹配的检验

假设表达式中含有3种括号：(),[],{}，其嵌套的顺序随意。检验括号是否匹配。

基本思想：在算法中设置一个栈，每读入一个括号，若是右括号，则或者与栈顶匹配的左括号相互消解，或者是不合法的情况；若是左括号，则直接压入栈中。若括号匹配，在算法的开始和结束时，栈都应该是空的。

代码：

/* * 判断表达式中的括号是否匹配，匹配输出Yes，否则输出No * {(zhang)+[lei]+{lei}={zhangleilei}} -> Yes * {(zhang)+[lei]+{lei}={zhangleilei(]}} -> Yes */#include <stdio.h>#include <stdbool.h>#include <malloc.h>#define STACK_INIT_SIZE 10		//存储空间初始分配量#define STACKINCREMENT 10		//存储空间分配增量typedef struct{	char *base;	char *top;	int stacksize;} SqStack;void InitStack(SqStack *s);bool GetTop(SqStack *s, char *c);bool StackEmpty(SqStack *s);bool Push(SqStack *s, char *c);bool Pop(SqStack *s, char *c);bool match(char a, char b);bool in(char c, char *ch);int main(){	SqStack s;	char ch,ch_prior;  	char *left = "([{";	char *right = ")]}";	bool flag = true;	InitStack(&s);	while (true)	{		if ((ch = getchar()) == ‘\n‘)			break;		if (in(ch, left))		//如果字符为左括号，进栈		{			Push(&s, &ch);		}		else if (in(ch, right))	//如果字符为右括号，判断栈顶元素是否存在并且与当前字符匹配		{			if (GetTop(&s, &ch_prior) && match(ch_prior, ch))			{				Pop(&s, &ch);			}			else			{				flag = false;				break;			}		}	}	if (flag == true)	{		puts("Yes");	}	else	{		puts("No");	}	return 0;}//初始化栈void InitStack(SqStack *s){	s->base = (char*)malloc(sizeof(char)*STACK_INIT_SIZE);	s->top = s->base;	s->stacksize = STACK_INIT_SIZE;}//获得栈顶元素bool GetTop(SqStack *s, char *c){	if (StackEmpty(s))		return false;	*c = *(s->top - 1);	return true;}//判断栈是否为空bool StackEmpty(SqStack *s){	if (s->base == s->top)		return true;	return false;}//进栈bool Push(SqStack *s, char *c){	//如果空间不够，增加空间的分配	if (s->top - s->base >= s->stacksize)	{		s->base = (char*)realloc(s->base, sizeof(char)*(s->stacksize + STACKINCREMENT));		s->stacksize = s->stacksize + STACKINCREMENT;	}	*(s->top++) = *c;	return true;}//出栈bool Pop(SqStack *s, char *c){	if (StackEmpty(s))		return false;	*c = *(--s->top);	return true;}//判断左括号a和右括号b是否相匹配bool match(char a, char b){	if (a == ‘(‘&&b == ‘)‘)		return true;	if (a == ‘[‘&&b == ‘]‘)		return true;	if (a == ‘{‘&&b == ‘}‘)		return true;	return false;}//判断字符c是否位于字符串ch中bool in(char c, char *ch){	while (*ch&&*ch != c)	ch++;	if (*ch) return true;	return false;}

2.     表达式求值

算符优先法求表达式的值。算符间的优先关系如下：

假设运算符a和b相继出现，则+、-、*和/为a时的优先性均低于’(’但高于’)’；为了满足从左算到右的规则，当a=b时，令a>b，’#’是表达式的结束符。为了算法简洁，在表达式的最左边也虚设一个’#’构成整个表达式的一对括号。

‘(’=’)’，表示当左右括号相遇时，括号内的运算已经完成。同理’#’=’#’表示整个表达式求值完毕。

在处理表达式前，首先设置两个栈：操作数栈(OPND)：用于寄存操作数和运算结果；运算符栈(OPTR)：用于寄存运算符。

算法的基本思想：

1)      首先置操作数栈为空栈，表达式起始符’#’为运算符栈的栈底元素；

2)      依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为’#’)。

代码：

/* * 输入算术表达式，运算符限定为"+ - * / ( )"，操作数限定为0~9。求表达式的值。 * 其中以#表示表达式的开始和结束。 * 输入：9+8-7*6/5*(4+3)-2+1# * 输出：-40 * 输入：((1+2)*3)+4*(5-2)# * 输出：21 */#include <stdio.h>#include <malloc.h>#include <stdbool.h>	//使用bool类型时需包含的头文件#include <assert.h>		//使用assert语句时需包含的头文件#define STACK_INIT_SIZE 20#define STACKINCREMENT 5typedef union{	char character;	int number;} ElemType;typedef struct{	ElemType *base;	ElemType *top;	int stacksize;} Stack;void InitStack(Stack *s);bool push(Stack *s, ElemType *ch);bool pop(Stack *s, ElemType *ch);ElemType *GetTop(Stack *s);bool in(char c, char *ch);char precede(char a, char b);int compute(int a, char oper, int b);int main(){	ElemType ch,ch_prior,temp;	//temp用于进栈和出栈的临时变量	ElemType left, right;	ElemType result;	Stack OPTR,OPND;	//运算符栈和操作数栈	char *num = "0123456789";	char *oper = "+-*/()#";		InitStack(&OPTR);	temp.character = ‘#‘;	push(&OPTR, &temp);	InitStack(&OPND);		ch.character = getchar();	//循环停止条件：栈顶元素为‘#‘，并且当前待进栈元素也为‘#‘。表明#号中间的表达式计算完毕。	while (!(GetTop(&OPTR)->character == ‘#‘ && ch.character == ‘#‘))	{		//若当前输入字符为数字，进操作数栈。继续读取下一个字符。		if (in(ch.character, num))		{			temp.number = ch.character - ‘0‘;			push(&OPND, &temp);			ch.character = getchar();		}		else if (in(ch.character, oper))//如果当前字符为运算符，比较栈顶运算符与当前运算符的优先级。		{			switch (precede(GetTop(&OPTR)->character, ch.character))			{				//若栈顶运算符优先级较高，则先计算中间值。				//注意，此时并未将当前运算符进栈，也没有读入下一个字符。				//而是在下一次while循环中继续将当前运算符和栈顶运算符做比较。			case ‘>‘:				pop(&OPND, &right);				pop(&OPND, &left);				pop(&OPTR, &ch_prior);				temp.number = compute(left.number, ch_prior.character, right.number);				push(&OPND,&temp);				break;				//若当前运算符优先级较高，将运算符进栈。继续读取下一个字符。			case ‘<‘:				push(&OPTR, &ch);				ch.character = getchar();				break;				//两个运算符优先级相同表明，栈顶运算符为‘(‘，当前运算符为‘)‘。此时将栈顶元素弹出。继续读取下一个字符。			case ‘=‘:				pop(&OPTR, &ch_prior);				ch.character = getchar();				break;			}		}	}	//此时，操作数栈只有一个元素，即为计算结果。	pop(&OPND, &result);	printf("%d", result.number);	return 0;}void InitStack(Stack *s){	s->base = (ElemType*)malloc(sizeof(ElemType)*STACK_INIT_SIZE);	s->top = s->base;	s->stacksize = STACK_INIT_SIZE;}bool push(Stack *s, ElemType *ch){	if (s->top - s->base >= s->stacksize)	{		s->base = (ElemType*)realloc(s->base, sizeof(ElemType)*(s->stacksize + STACKINCREMENT));		s->stacksize = s->stacksize + STACKINCREMENT;	}	*(s->top++) = *ch;	return true;}bool pop(Stack *s, ElemType *ch){	if (s->top == s->base)	//空栈		return false;	*ch = *(--s->top);	return true;}ElemType* GetTop(Stack *s){	if (s->top == s->base)		return NULL;	return (s->top - 1);}//检验字符c是否位于字符串ch中。bool in(char c, char *ch){	while (*ch&&*ch != c)		ch++;	if (*ch)		return true;	return false;}//比较运算符a和b的优先级。char precede(char a, char b){	switch (a)	{	case ‘+‘:		if (in(b, "+-)#"))			return ‘>‘;		else if (in(b, "*/("))			return ‘<‘;		break;	case ‘-‘:		if (in(b, "+-)#"))			return ‘>‘;		else if (in(b, "*/("))			return ‘<‘;		break;	case ‘*‘:		if (in(b, "+-*/)#"))			return ‘>‘;		else if (in(b, "("))			return ‘<‘;		break;	case ‘/‘:		if (in(b, "+-*/)#"))			return ‘>‘;		else if (in(b, "("))			return ‘<‘;		break;	case ‘(‘:		if (in(b, "+-*/("))			return ‘<‘;		else if (in(b, ")"))			return ‘=‘;		break;	case ‘)‘:		if (in(b, "+-*/)#"))			return ‘>‘;		break;	case ‘#‘:		if (in(b, "+-*/("))			return ‘<‘;		else if (in(b, "#"))			return ‘=‘;		break;	}}//用于计算中间值。int compute(int a, char oper, int b){	switch (oper)	{	case ‘+‘:		return a + b;	case ‘-‘:		return a - b;	case ‘*‘:		return a * b;	case ‘/‘:		assert(b != 0);		return a / b;	}}

pdf下载：http://pan.baidu.com/s/1bnhFiqj