Status match(char *str)/* 若str是属该模式的字符序列，*/ /* 则返回TRUE，否则返回FALSE */ {
SqStack s; SElemType e; InitStack(s); int i=0;
while(str[i]!='&'&&str[i]!='@') {
Push(s,str[i]); i++; }
if(str[i]=='@') return FALSE;
if(str[i]=='&') i++; while(str[i]!='@') {
Pop(s,e); if(e!=str[i]) return FALSE; i++; }
if(StackEmpty(s)&&str[i]=='@') return TRUE; else return FALSE; }
3.18② 试写一个判别表达式中开、闭括号是否配对出现的算法。 Status MatchCheck(SqList exp)
/* 顺序表exp表示表达式； */ /* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ /* 注：本函数不使用栈 */ { int i=0; int s=0;
while(exp.elem[i]!='\\0') {
if(exp.elem[i]=='(') s++;
if(exp.elem[i]==')') s--; } if(s==0)
return TRUE;
else return FALSE; }
实现下列函数：
Status MatchCheck(SqList exp);
/* 顺序表exp表示表达式； */
/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ /* 注：本函数不使用栈 */ 顺序表类型定义如下： typedef struct {
ElemType *elem; int length; int listsize; } SqList; // 顺序表
◆3.19④ 假设一个算术表达式中可以包含三种括号：圆括号\和\，方括号\和\和花括号\和\，且这三种括号可按任意的次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。 实现下列函数：
Status MatchCheck(SqList exp);
/* 顺序表exp表示表达式； */ /* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ 顺序表类型定义如下： typedef struct {
ElemType *elem; int length; int listsize; } SqList; // 顺序表
Stack是一个已实现的栈。 可使用的相关类型和函数：
typedef char SElemType; // 栈Stack的元素类型 Status InitStack(Stack &s);
Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s);
Status GetTop(Stack s, SElemType &e); Status MatchCheck(SqList exp)
/* 顺序表exp表示表达式； */ /* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ { SqStack Q;
int i=0; SElemType e; while(exp.elem[i]!='\\0') {
if(exp.elem[i]=='('||exp.elem[i]=='['||exp.elem[i]=='{') Push(Q,exp.elem[i]);
else if(exp.elem[i]==')'||exp.elem[i]==']'||exp.elem[i]=='}') { if(!StackEmpty(Q)) Pop(Q,e) ; else return FALSE;
if(e=='('&&exp.elem[i]!=')') return ERROR;
if(e=='['&&exp.elem[i]!=']') return ERROR;
if(e=='{'&&exp.elem[i]!='}') return ERROR; } i++; }
if(StackEmpty(Q)) return TRUE;
else return FALSE; }
3.20③ 假设以二维数组g(1..m,1..n)表示一个图像区域，g[i,j]表示该区域中点(i,j)所具颜色，其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色区域的点。
实现下列函数：
void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0); /* 在g[1..m][1..n]中，将元素g[i0][j0] */
/* 所在的同色区域的颜色置换为颜色c */ 表示图像区域的类型定义如下： typedef char GTYPE[m+1][n+1]; Stack是一个已实现的栈。 可使用的相关类型和函数：
typedef char SElemType; // 栈Stack的元素类型 Status StackInit(Stack &s, int initsize); Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s);
Status GetTop(Stack s, SElemType &e); void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0) /* 在g[1..m][1..n]中，将元素g[i0][j0] */
/* 所在的同色区域的颜色置换为颜色c */ { Stack s;
int row,col;//行，列 InitStack(s); char f;
f = g[i0][j0]; g[i0][j0] = c; Push( s, i0); Push( s, j0);
while( !StackEmpty(s) ){ Pop( s, col ); Pop( s, row );
if( row > 1 && g[row-1][col] == f ){ Push( s, row-1); Push( s, col); g[row-1][col] = c; }
if( row < m && g[row+1][col] ==f ){ Push( s, row+1); Push( s, col);
g[row+1][col] = c; }
if( col > 1&& g[row][col-1] == f ){ Push( s, row); Push( s, col-1); g[row][col-1] = c; }
if( col < n && g[row][col+1] == f ){ Push( s, row ); Push( s, col+1 ); g[row][col+1] = c; } } }
◆3.21③ 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。 实现下列函数：
char *RPExpression(char *e);/* 返回表达式e的逆波兰式 */ Stack是一个已实现的栈。 可使用的相关类型和函数：
typedef char SElemType; // 栈Stack的元素类型 Status InitStack(Stack &s);
Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s); int precede(char op) { int x; switch(op) {
case '*': x=2; break; case '/': x=2; break; case '+': x=1; break; case '-': x=1; break; default : x=0; }
return x; }
char *RPExpression(char *e)
{/* 返回表达式e的逆波兰式 */ char *c;
c=(char*)malloc(sizeof(char)*20); //不能用char c[] Stack s1; InitStack(s1);
int i=0,j=0; char ch; Push(s1,'@'); ch=e[i++]; while(ch!= 0) {
if(ch=='(') {
Push(s1,ch); ch=e[i++]; }
else if(ch==')') {
while(Top(s1)!='(') {
Pop(s1,c[j++]); }
/* to[j++]=pop(&s1);*/ Pop(s1,ch); ch=e[i++]; }
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/') {
char w; w=Top(s1);
while(precede(w)>=precede(ch)) {
Pop(s1,c[j++]); w=Top(s1); }
Push(s1,ch); ch=e[i++]; } else {
//while((ch<='z'&&ch>='a')||(ch<='Z' c[j++]=ch; ch=e[i++]; //}
//c[j++]=' '; } }
Pop(s1,ch); while(ch!='@') {
c[j++]=ch;
&& ch>='A')){