使用顺序栈完成表达式括号（大，中，小）的平衡检测

为什么要使用栈完成：刚开始我想利用标志变量来完成这项工作，后面发现了使用栈完成符号平衡检测的好处，因为封闭符号（如右括号）总是与最近的开放符号匹配（如左括号），所有一旦遇到封闭符号如果栈顶元素不是与之匹配的开放符号则说明这个表达式的符号不平衡，在符号的平衡检测中充分体现了栈这种先进后出表的作用，且利用栈来完成平衡符号的检测的算法时间复杂度是O（1）。

**算法：**遇到开放符号（如左括号）则入栈，遇到封闭符号（如右括号）则出栈并检查弹出的符号是否是与这个封闭符号匹配的开放符号，如果不是则说明符号不匹配；最后循环结束时检查栈内元素，如果栈内有元素则说明符号不匹配，如果循环顺利结束且栈内没有元素则说明表达式符号匹配。

**实现代码：

#include<iostream>
const int stacksize=100;
typedef struct Stack{
	char bracket[stacksize];
	int top=-1;
}Stack;
using namespace std;
int Isempty(Stack*);        //判栈空
int Isfull(Stack*);         //判栈满
int Push(Stack*,char);      //入栈
char Pop(Stack*);           //出栈
void Input(string&);        //输入表达式
void Balance(string);       //平衡符号检测
int main(void){
	string fix;
	Input(fix);
	Balance(fix);
	return 0;
}
int Isempty(Stack* p){
	return p->top==-1;
}
int Isfull(Stack* p){
	return p->top==stacksize-1;
}
int Push(Stack* p,char ch){
	if(Isfull(p)){
		cout<<"The stack is full"<<endl;
		return 0;
	}
	p->bracket[++p->top]=ch;
	return 1;
}
char Pop(Stack* p){
	if(Isempty(p)){
		cout<<"The stack is empty"<<endl;
		return 0;
	}
	return p->bracket[p->top--];
}
void Input(string& fix){
	cout<<"Please input a fix"<<endl;
	getline(cin,fix);
}
void Balance(string fix){
	Stack p;
	int i;
	char temp;
	for(i=0;i<fix.size();i++){
		if(fix[i]=='('){
			Push(&p,fix[i]);
		}else if(fix[i]=='['){
			Push(&p,fix[i]);
		}else if(fix[i]=='{'){
			Push(&p,fix[i]);
		}else if(fix[i]==')'){
			temp=Pop(&p);
			if(temp!='('){
				cout<<"The fix isn't balance"<<endl;
				return;
			}
		}else if(fix[i]==']'){
			temp=Pop(&p);
			if(temp!=']'){
				cout<<"The fix isn't balance"<<endl;
				return;
			}
		}else if(fix[i]=='}'){
			temp=Pop(&p);
			if(temp!='}'){
				cout<<"The fix isn't balance"<<endl;
				return;
			}
		}
	}
	if(!Isempty(&p)) cout<<"The fix isn't balance"<<endl;
	else cout<<"The fix is balance"<<endl;
}

输出样例：

Please input a fix
1+2+3+4+5=15
The fix is balance

Please input a fix
{==[===(==)]}
The fix is balance

Please input a fix
1+2+{9（-9])}
The fix isn't balance