判别括号匹配

判别括号匹配

一．问题描述

一个算术表达式含圆括号、中括号、花括号,且它们可任意嵌套使用。写一程序，判断任一算术表达式中所含括号是否正确配对。 （1）表达式从键盘输入。 （2）利用栈求解此问题。 （3） 测试用例自己设计。 二．设计

本实验需要用堆栈进行解决。首先建立堆栈 typedef struct { Char stack[M]; int top;

}SeqStack;//定义seqstack堆栈结构体 实验中也同时用到了堆栈的各种基本操作。 初始化堆栈

void Stackinit(SeqStack *s) { s->top = 0; } 进栈

int Stackpush(SeqStack *s, char x) { if (s->top>= maxsize) { cout << \"堆栈已满无法插入！\\n\"; return 0; } else { s->stack[s->top] = x; s->top++; return 1; } } 出栈

int Stackpop(SeqStack *s, char *x) { if (s->top <= 0) { cout << \"堆栈已空无数据出栈！\\n\"; return 0;

} else { s->top--; *x = s->stack[s->top]; return 1; } }

判断堆栈是否为空

int Stacknotempty(SeqStack s) { if (s.top <= 0) return 0; else return 1; }

取栈顶元素

int Stacktop(SeqStack s, char *x) { if (s.top <= 0) { cout << \"堆栈为空！\\n\"; return 0; } else { *x = s.stack[s.top - 1]; return 1; } }

判断函数;

void testcorrect(char a[], int n) { SeqStack mystack; int i; char c; int count=0; Stackinit(&mystack);//初始化堆栈 for (i = 0; i <= n; i++) { if ((a[i] == '(') || (a[i] == '[') || (a[i] == '{'))

Stackpush(&mystack, a[i]);//若果是前括弧，进栈 else if (a[i] == ')' && Stacknotempty(mystack) && Stacktop(mystack, &c) && c == '(') Stackpop(&mystack, &c);//a[i]为\")\"栈顶为\"(\"时出栈 else if (a[i] == ')'&&Stacknotempty(mystack) && Stacktop(mystack, &c) && c != '(') { cout << \"左右括弧配对不正确！\\n\"; return; }//当a[i]与栈顶括弧不匹配，输出错误提示 else if (a[i] == ']'&&Stacknotempty(mystack) && Stacktop(mystack, &c) && c == '[') Stackpop(&mystack, &c);//a[i]为\"]\"栈顶为\"[\"时出栈 else if (a[i] == ']'&&Stacknotempty(mystack) && Stacktop(mystack, &c) && c != '[') { cout << \"左右括弧配对不正确！\\n\"; return; }//当a[i]与栈顶括弧不匹配，输出错误提示 else if (a[i] == '}'&&Stacknotempty(mystack) && Stacktop(mystack, &c) && c == '{') Stackpop(&mystack, &c);//a[i]为\栈顶为\"{\"时出栈 else if (a[i] == '}'&&Stacknotempty(mystack) && Stacktop(mystack, &c) && c != '{') { cout << \"左右括弧配对不正确！\\n\"; return; }//当a[i]与栈顶括弧不匹配，输出错误提示 else if (((a[i] == ')') || (a[i] == ']') || a[i] == '}') && !Stacknotempty(mystack)) { cout << \"存在右括弧无左括弧匹配！\\n\"; return; }//当a[i]为右括弧但栈内已无括弧时输出错误提示 } if (Stacknotempty(mystack)) cout << \"存在左括弧无右括弧匹配\\n\";//当i=n但栈内依旧有括弧时，输出错误提示 else cout << \"左右括弧匹配正确！\\n\"; }

主要算法框图：

三．调试

为检验程序是否可行，分别输入以下括弧序列： 1.{[（]）}括弧配对错误

2.。{[（）左括弧多于右括弧

3.（）））右括弧多于左括弧

4.{[（）]}括弧配对正确

经检验，程序运行正确。

测试括弧序列1时，程序显示括弧匹配正确，与实际结果不符。多次试验后发现中文与英文输入法的括弧是不一样的。此问题可在输入括弧序列时避免，也可在代码中添加中英两种括弧进行匹配。

四．经验和体会

本次实验中，判可定义count统计右括弧多于左括弧的个数，mystack.Top可作为左括弧多于右括弧的个数。

else if (((a[i] == ')') || (a[i] == ']') || a[i] == '}') && !Stacknotempty(mystack)) { Count++； }//当a[i]为右括弧但栈内已无括弧时计数 If(count) {

Cout<<”右括弧比左括弧多”<if (Stacknotempty(mystack)) Cout<<”左括弧比右括弧多”<