题解：2018级算法第一次上机 C1-pair

题目描述

北航2018级软件学院算法分析与设计第一次上机第三题

样例

实现解释

题目类型：

　　这类题目其实就是典型的递归分析语句形式的问题，也是编译原理课程中语法分析的重要方法之一。

解决方案：

　　为了解决这类问题，可以利用多函数递归调用的方法解决，针对本题即：编写两个函数分别用于判断是否为pair以及是否为type。（这里的是否为pair是指判断是否为一个完整的pair结构体）

　　判断pair函数的构造原因是作为首次调用的函数，在其中调用其他的判断函数，并且由题意可知在判断type时也是需要判断pair，因此需要pair的判断程序能被再次调用，所以构造为一个完整的函数。

　　而编写type判断函数的原因是它相比于其他出现的内容（这里指一个int），type是多选择（或者说可分解的）的，它可以转化为两种形式：一个完整的pair，单独的int，对于这两种选择又都有不同的去向，所以通过构造函数可以更好的判断句子的组成。

程序本身：

　　回到程序本身，如何递归判断以及形成输出内容：这里推荐一个双向行走的方式，用两个字符数组或者两个string存储输入的字符串和要输出的字符串。为他们分别设定标记下标位置的向量。对于输入的字符串只需一次加一，不断读入后面的字符然后判断进入哪个判断程序即可；对输出的字符串则需要在判断结束后为其添加对应的输出内容（除了pair，int注意还要有<>,等字符）。

　　具体实现可参考完整代码，这类题目结合代码参考较为容易。

坑点

1.后移下标判断字符串时多次移动，这里需要自己设定一个规则，即在函数的开头进行下标的移动还是在调用函数前进行下标的移动，否则容易出现略过字符的情况。

2.判断pair（即最初始的pair判断）时，注意一个pair判断完毕后需要进行再一步的判断，因为此时有三种情况：（1）pair是type转化为的pair（2）pair是最初始的pair且后续没有其他字符（3）pair是最初始的但后续出现其他字符。显然第三种是错误的，因为题目说了只有一个，所以需要在pair判断结束后依据下标对第三种情况进行筛选。（这里采用的是在初始调用的pair判断函数返回后判断下标和输入字符串的长度的关系，也是比较推荐的一种）

完整代码

#include<iostream>

#include<cstdio>

using namespace std;

int num;//输入字符串移动下标

int endnum;//输出字符串移动下标

string endString[3000];//输出字符串

//只能前面定义后面防止代码，因为涉及互相调用

bool checkT(string *a);//type判断函数

bool checkP(string *a);//pair判断函数

int main()

{

	int t;

	cin >> t;

	while(t--)

	{

		int n;

		cin >> n;

		string temp;

		string *a = new string[4000];

		int i = 0;

		for(int i =0;i<n;i++)

		{

			cin >> temp;

			a[i] = temp;

			//这里是一次传入一个字符串，如利用char数组可以传入一个P或者I这种首字母

		}

		num = 0;

		endnum = 0;

		if(checkP(a))

		{

			if(num == n-1)//判断一个pair后是否还有内容

			{

				for(int i = 0;i<endnum;i++)

				{

					cout << endString[i];

				}

			}

			else

			{

				cout << "Error occurred";

			}

		}

		else

		{

			cout << "Error occurred";

		}

		cout << endl;

		delete [] a;

	}

	return 0;

}

bool checkT(string *a)//type判断函数

{

	if(a[num] == "int")

	{

		endString[endnum++] = "int";

		return true;

	}

	if(a[num] == "pair")

	{

		if(checkP(a))

		{

			return true;

		}

	}

	return false;

}

bool checkP(string *a)//pair判断函数

{

	if(a[num] == "pair")

	{

		num++;//采取的是调用函数前移动下标num的形式

		endString[endnum++] = "pair";

		endString[endnum++] = "<";

		//输出字符串的增加直接endnum++个人感觉是最简便的形式

		if(checkT(a))

		{

			num++;

			endString[endnum++] = ",";

			if(checkT(a))

			{

				endString[endnum++] = ">";

				return true;

			}

		}

	}

	return false;

}

巴特西

题解：2018级算法第一次上机 C1-pair

题目描述

样例

实现解释

坑点

完整代码

最新文章

热门文章