符号匹配问题

1.内容要求

设 C 语言程序代码中包含如下符号/* */，()，[]，{}，检测一段 C 代码中上述符号是否正确（能正确配对、正确嵌套、没有出现交叉）。

2.主程序的流程图

3.程序模块之间的层次(调用)关系

在主函数中，创建一个字符匹配的对象，将栈初始化为空栈，在输入要检验的一段代码之后，调用函数MatchBrackets进行对符号的匹配，此时需要将遇到的‘{’，‘[’，‘(’，‘/*’，进行入栈的判断，需要调用入栈的函数Push，如果遇到与之匹配的符号，就需要进行当前的栈顶元素进行比较，这时就需要调用取栈顶元素的函数，即GetTop函数，当两者比较相同时，则需要调用出栈函数，即Pop函数。

4.程序流程图

5.思维导图

#pragma once//链栈
#include<iostream>
#include<string> 
using namespace std;
const int MAXSIZE=100;
template <class T>
struct Node {
	T data;//数据域
	Node<T>* next;//指针域
};
template <class T>
class LinkStack {
public:
	LinkStack();   //构造函数，初始化一个空链栈 
	~LinkStack();   //析构函数，释放链栈各结点的存储空间  
	void Push(T x);  //入栈操作，将元素X入栈  
	T Pop();       //出栈操作，将栈顶元素出栈  
	T GetPop();		//取栈顶元素  
	int Empty();	//判空操作，判断链栈是否为空栈  
	void MatchBrackets(string res);//判断一段代码是否符号匹配 
private:
	Node<T> *top;//栈顶指针即链栈的头指针
};
//构造函数，初始化一个空链栈
template <class T>
LinkStack<T>::LinkStack() {
	top = NULL; 
}
//析构函数，释放链栈各结点的存储空间 
template <class T>
LinkStack<T>::~LinkStack() {
	Node<T>* p = NULL;
	while (top != NULL) {
		p = top;
		top = top->next;
		delete p;
	}
}
//入栈操作，将元素X入栈 
template <class T>
void LinkStack<T>::Push(T x) {
	Node<T>* s = NULL;
	s = new Node<T>;
	s->data = x;
	s->next = top;
	top = s;//将结点s插在栈顶 
}
//出栈操作，将栈顶元素出栈 
template <class T>
T LinkStack<T>::Pop() {
	Node<T>* p = NULL;
	T x;
	if (top == NULL) { throw "下溢"; }
	x = top->data;//暂存栈顶元素 
	p = top;      //将栈顶元素摘链 
	top = top->next;
	delete p;
	return x;
}
//取栈顶元素
template <class T>
T LinkStack<T>::GetPop() {
	if (top != NULL) { return top->data; }
}
//判空操作，判断链栈是否为空栈
template <class T>
int LinkStack<T>::Empty() {
	
	if (top == NULL) { return 1; }
	else { return 0; }
}
//判断一段代码是否符号正确配对、正确嵌套、出现交叉
template <class T>
void LinkStack<T>::MatchBrackets(string res){
	for (int i = 0; i < res.length(); i++)
	{
		if (res[i] == '/' && res[i + 1] == '*' && (i + 1 < res.length()))
		{
			Push(res.substr(i, 2));//获得字符串res中从第i位开始的长度为2的字符串
			i++;
		}
		else if (res[i] == '*' && res[i + 1] == '/' && (i + 1 < res.length()))
		{
			if (!Empty() && GetPop() == "/*")
				// 若为*/，且栈不为空，栈内还有/*与之配对，则/*出栈
				Pop();//出栈
			else
				//若没有的话，配对失败，按照题目要求输出
			{
				cout << "该代码无法正常执行！" << endl;
				if (Empty()) //如果栈为空 
					cout << "*/匹配不正常";
				//匹配不正常左符号
				else
					cout << GetPop() << "匹配不正常";
				//栈内的符号没有配对成功
				return ;
			}
			i++;
		}
		else if (res[i] == '(' || res[i] == '{' || res[i] == '[')
		{
			Push(string(1, res[i])); //用1个字符res[i]初始化
		}
		else if (res[i] == '}')
		{
			if (!Empty() && GetPop() == "{")
				Pop();
			else
			{
				cout << "该代码无法正常执行！" << endl;
				if (Empty())
					cout << res[i]<< "匹配不正常" ;
				else
					cout << GetPop() << "匹配不正常";
				return ;
			}
		}

		else if (res[i] == ']')
		{
			if (!Empty() && GetPop() == "[")
				Pop();
			else
			{
				cout << "该代码无法正常执行！" << endl;
				if (Empty())
					cout <<  res[i] <<"匹配不正常";
				else
					cout << GetPop() << "匹配不正常";
				return ;
			}
		}

		else if (res[i] == ')')
		{
			if (!Empty() && GetPop() == "(")
				Pop();
			else
			{
				cout << "该代码无法正常执行！" << endl;
				if (Empty())
					cout << "匹配不正常" << res[i];
				else
					cout <<GetPop() << "匹配不正常";
				return ;
			}
		}
	}
	if (Empty())
		cout << "该代码能正常执行！";
	else
	{
		cout << "该代码无法正常执行！" << endl;
		cout << GetPop() << "匹配不正常";
	}
}

int main()
{
	while(true){
		cout<<"请输入一个算数表达式:"<<endl;
		LinkStack<string> st;//创建链栈的对象 
		string s;
		string res;
		//将输入的每一行字符串进行叠加 
		while (1){
			cin >> s;
			if (s == "."){break;}
			res = res + s;
		}
		//将所有输入的字符串进行符号检验是否正确配对、正确嵌套、出现交叉等 
		st.MatchBrackets(res);
		cout<<"\n"<<endl;
	}
	return 0;
}