最新消息:网站改版咯

括号匹配算法

算法 Yovae 2279浏览

括号匹配问题

  • 问题描述:
  • 在对高级语言编写的程序进行编译时会遇到表达式或字符串的括号匹配问题。例如C++
    程序中左、右花括号“{”和“}”的匹配问题。表达式(字符串)的括号匹配问题要求确定
    一给定表达式(字符串)中左、右括号的匹配情况。例如,表达式(x*(x+y)-z)在位置1 和4
    处有左括号,在位置8 和11 处有右括号。位置1 处的左括号与位置11 处的右括号相匹配;
    位置4 处的左括号与位置8 处的右括号相匹配。而在表达式(x+y)*z)(中,位置8处的右括号
    没有可匹配的左括号,位置9处的左括号没有可匹配的右括号。
  • 编程任务:
  • 给定一个 C++源程序,编程计算其中括号“<”和“>”;“(”和“)”;“[”和“]”;“{”
    和“}”的匹配情况。
    将括号“<”和“>”;“( ”和“)”;“[ ”和“]”;“{ ”和“}”的匹配情况输出到文件output.txt。
    文件的第1行是括号“<”和“>”的匹配情况,如果匹配则输出“Yes”,否则输出“No”;
    文件的第2 行是括号“(”和“)”的匹配情况,如果匹配则输出“Yes”,否则输出“No”;
    文件的第3 行是括号“[”和“]”的匹配情况,如果匹配则输出“Yes”,否则输出“No”;
    文件的第4行是括号“{”和“}”的匹配情况,如果匹配则输出“Yes”,否则输出“No”。
  • 数据输入:
  • C++源程序文件名为prog.cpp。
  • 输入文件示例:
  • prog.cpp output.txt
    #include
    void Output(int NowOut, int Track, int& Last)
    {
    if (NowOut == Last) Last = 0;
    }
    bool Hold(int c, int last[], int track[], int k)
    {
    for (int i = 1; i != k; i++) // find best track
    if (last[i]) {
    BestLast = last[i];
    BestTrack = i;
    }
    return true;
    }
  • «结果输出:
  • 输出文件示例:
    Yes
    Yes
    Yes
    Yes
/*
  括号匹配算法 V1
  08计科2班  叶有为 081914067
   2010
*/
#include <iostream>
#include <fstream>
#define size 30
using namespace std;

int main()
{
	ifstream inf("prog.cpp");
	ofstream outf("output.txt");
	char buf[1024],ch;
	int hc[4][size]={0},a[4]={1,1,1,1},x,i=0; 
	
	while(!inf.fail())
	{
         	inf>>buf;
			i=0;
			while(ch=buf[i++])
			switch(ch)
			{
			case '<':
				hc[0][a[0]++]=1;
				break;
			case '>':
				if(a[0]==1)
				{
				hc[0][0]=-1;
				hc[0][1]=-1;
				a[0]++;
				}
				else
				hc[0][a[0]++]=-1;
				break;
			case '(':
				hc[1][a[1]++]=1;
				break;
			case ')':
				if(a[1]==1)
				{
                hc[1][0]=-1;
				hc[1][1]=-1;
				a[1]++;
				}
				else
				hc[1][a[1]++]=-1;
				break;
			case '[':
				hc[2][a[2]++]=1;
				break;
			case ']':
				if(a[2]==1)
				{
				hc[2][0]=-1;
				hc[2][1]=-1;
				a[2]++;
				}
				else
			    hc[2][a[2]++]=-1;
				break;
			case '{':
				hc[3][a[3]++]=1;
				break;
			case '}':
				if(a[3]==1)
				{
				hc[3][0]=-1;
				hc[3][1]=-1;
				a[3]++;
				}
				else
				hc[3][a[3]++]=-1;
				break;
			}
	}
 /*
for(i=0;i<4;i++)
   {
       x=(a[i]-1)%2;
	   if((hc[i][0]>=0)&&(!x))
	   {
		   int m=a[i]-1;
		   for(int j=1;j<=(a[i]-1)/2;j++)
		   {
                 if((hc[i][j]+hc[i][m--])!=0) hc[i][0]=-1;
		   }
	   }
	   else
		   hc[i][0]=-1;
   }
   更加智能的匹配算法(未完成)。
*/
	int sum=0;
   for(i=0;i<4;i++)
   {
       x=(a[i]-1)%2;
	   if((hc[i][0]>=0)&&(!x))
	   {
		   int m=a[i]-1;
		   for(int j=1;j<=a[i]-1;j++)
		   {
                 sum+=hc[i][j];
		   }
		   
	   }
	   else
		   hc[i][0]=-1;
	   if(sum!=0) hc[i][0]=-1;
   }
   /*for(i=0;i<4;i++)
	  {for(int j=0;j<30;j++)
		  printf("%2d",hc[i][j]);
        cout<<endl;}
		用于调试查看矩阵数值变化
	*/
   for(i=0;i<4;i++)
   {
	   if(hc[i][0]>=0)

           outf<<"Yes"<<endl;
	   else
		   outf<<"No"<<endl;
   }
   inf.close();
   outf.close();
   return 1;

}

转载请注明:Yovae Studio » 括号匹配算法