预测分析法判断算术表达式的正确性

通过文件input.txt输入

源代码

#include 
#include 
#include 
#include 
using namespace std;
map > ma;
map endlist;
vector vc;
string str[100];
FILE* fin, * fout;
int  lookahead;
char ch[100];
void init();
void match(char c);
void check();
void error();
void ditui(string t);
void guiyue(string t);
void init() {
	ma["E"]["i"] = "TE'";                                                ma["E"]["("] = "TE'";
	ma["E'"]["+"] = "+TE'";       ma["E'"]["-"] = "-TE'";                                       ma["E'"][")"] = " &"; ma["E'"]["#"] = "&";
	ma["T"]["i"] = "FT'";                                                ma["T"]["("] = "FT'";
	ma["T'"]["+"] = "&"; ma["T'"]["-"] = "&"; ma["T'"]["*"] = "*FT'"; ma["T'"]["/"] = "/FT'";  ma["T'"][")"] = "&"; ma["T'"]["#"] = "&";
	ma["F"]["i"] = "i"; ma["F"]["("] = "(E)"; ma["T'"]["/"] = "/ET'";

	//结束字符
	endlist["i"] = "F->i";
	endlist["+"] = "E'->+TE'";
	endlist["*"] = "T'->*FT'";
	endlist["("] = "F->(E)";
	endlist["-"] = "F->&";
	endlist[")"] = "T'->&";
	endlist["/"] = "T->/FT'";


	//压入#
	vc.push_back("#");
	vc.push_back("E");


}
void error() {

	throw "fail";
}

void ditui(string s)
{
	cout << "可以匹配s:" << s << endl;
	bool f = 0;//不用等待
	string t;

	//从后向前
	for (int i = s.size() - 1; i >= 0; i--) {

		t = s[i];
		//空就不用压入栈中
		if (t == "&")
		{
			return;

		}
		//要等待下一个字符的进入
		if (t == "'")
		{
			f = 1;
		}
		else
		{
			//前面的一个字符是‘需要一同压入栈中
			if (f)
			{
				vc.push_back(t + "'");
				cout << "压入:" << t + "'" << endl;
				f = 0;
			}
			else {
				vc.push_back(t);
				cout << "压入:" << t << endl;
			}

		}


	}

}
void guiyue(string t)
{
	cout << "匹配：" << endlist[t] << endl;
	//没有到到#，指针就继续向后；
	if (lookahead != '#')
		lookahead += 1;
}
void check() {
	//没有到匹配到#结束
	while (vc.back() != "#") {
		string l = vc.back();//栈顶
		string r = str[lookahead];//当前的匹配字符
		cout << endl;
		cout << "匹配符号：" << str[lookahead] << endl;
		cout << "栈顶" << l << endl;
		vc.pop_back();



		//不是终结符
		if (endlist[l] == "") {
			if (ma[l][r] == "" && ma[l][r] != "&") error();
			ditui(ma[l][r]);
		}
		//终结符
		else
		{
			//判断结束符是否相等
			if (l == r)
			{
				//相等下标就后移
				guiyue(l);
			}
			else
			{
				error();
			}
		}
	}
}
int main()
{
	fin = fopen("input.txt", "r");
	fout = fopen("output.txt", "w+");
	while (fscanf(fin, "%s", ch) != EOF) {
		//初始化构建单词表ma，和结束符表endlist
		init();
		//把输入的字符串存入str字符串数组中
		for (int i = 0; i < strlen(ch); i++) {
			str[i] += ch[i];
		}

		//表示str中的现在匹配的字符串
		lookahead = 0;

		//接受异常
		try {
			check();
			cout << "yes" << endl;
		}
		catch (const char* msg) {
			cout << msg << endl;//输出异常
		}
	}
	fclose(fin);
	fclose(fout);
	return 0;
}

input.txt

i/(i-i)#

输出

匹配符号：i
栈顶E
可以匹配s:TE'
压入:E'
压入:T

匹配符号：i
栈顶T
可以匹配s:FT'
压入:T'
压入:F

匹配符号：i
栈顶F
可以匹配s:i
压入:i

匹配符号：i
栈顶i
匹配：F->i

匹配符号：+
栈顶T'
可以匹配s:&

匹配符号：+
栈顶E'
可以匹配s:+TE'
压入:E'
压入:T
压入:+

匹配符号：+
栈顶+
匹配：E'->+TE'

匹配符号：i
栈顶T
可以匹配s:FT'
压入:T'
压入:F

匹配符号：i
栈顶F
可以匹配s:i
压入:i

匹配符号：i
栈顶i
匹配：F->i

匹配符号：#
栈顶T'
可以匹配s:&

匹配符号：#
栈顶E'
可以匹配s:&
yes

预测分析法判断算术表达式的正确性

C/C++/C#相关栏目本月热门文章