arithmetic.cpp

LR(1)文法实现四则运算程序

/************************************************************************/
/* 文件描述: LR(1)文法实现四则运算
   作者    : 谢伟
   时间    : 16/12/2007                                                 */
/************************************************************************/
#include "stdafx.h"
#include <stack>
#include <string>
#include <iostream>
#include <math.h>
#include <cassert>

using namespace std;

typedef   int STATUS;
#define   REDUCE    0
#define   MOVEIN    1
#define   ACCEPT    2
#define   ERROR     3

//这里使用的是二义性方法构造的LR(1)分析表
//E->E+E|E-E|E*E|E/E|i
const  string ACTION[][6]={
//   +/-      *//     (       )      i    #
	{"",      "",   "S2",    "",   "S3",  ""},  //0
	{"S4",  "S5",     "",    "",     "",  "acc"},//1
	{"",      "",   "S2",    "",   "S3",  ""},  //2
	{"r4",  "r4",     "",  "r4",     "",  "r4"},//3
	{"",      "",   "S2",    "",   "S3",  ""},  //4
	{"",      "",   "S2",    "",   "S3",  ""},  //5
	{"S4",  "S5",     "",  "S9",     "",  ""},  //6
	{"r1",  "S5",     "",  "r1",     "",  "r1"},//7
	{"r2",  "r2",     "",  "r2",     "",  "r2"},//8
	{"r3",  "r3",     "",  "r3",     "",  "r3"} //9	
};
const  int     GOTO[]={
	1,//0
	0,//1
	6,//2
	0,//3
	7,//4
	8,//5
	0,//6
	0,//7
	0,//8
	0,//9
};

void      Reduction( stack<char>   &symbol,
					 stack<double> &data, 
					 stack<STATUS> &status, 
					 int r_flags );
bool    ExpCalculation( string &exp, double &value );

int main(int argc, char* argv[])
{
	string    exp;
	char      ch[200];
	double    value;
	while(true)
	{
	cout << "Please input the expression:(press Q or q to exit)" << endl;
	cout << ">>";
	cin.getline(ch, 200);
	exp = ch;
	if(exp.size() == 1 && (exp[0] == 'q'||exp[0] == 'Q'))
		exit(0);
	else
	{
	if(ExpCalculation(exp, value))
		cout << "the value is: " << value << endl;
	else 
		cout << "error" << endl;
	}
	}
	return 0;
}

void    Reduction(stack<char> &symbol, stack<double> & data, stack<STATUS> &status, int r_flags )
{
	double  d1 = 0;
	double  d2 = 0;
	switch(r_flags)
	{
	case 1://E->E+E|E-E
		d1= data.top();
		data.pop();
		d2 =data.top();
		data.pop();
		if(symbol.top() == '+')
		{
			d1 = d1 + d2;
		}
		else d1= d2 - d1;

		data.push(d1);
		symbol.pop();
		status.pop();
		status.pop();
		status.pop();
		status.push(GOTO[status.top()]);
		break;

	case 2://E->E*E|E/E
		d1= data.top();
		data.pop();
		d2 =data.top();
		data.pop();
		if(symbol.top() == '*')
		{
			d1 =d1 * d2;
		}
		else {
			assert(d1);
			d1= d2 / d1;
		}

		data.push(d1);
		symbol.pop();
		status.pop();
		status.pop();
		status.pop();
		status.push(GOTO[status.top()]);
		break;

	case 3://E->(E)
		symbol.pop();
		symbol.pop();
		status.pop();
		status.pop();
		status.pop();
		status.push(GOTO[status.top()]);
		break;

	case 4:	//E->i
		status.pop();
		status.push(GOTO[status.top()]);
		 break;
	}
}

bool    ExpCalculation( string &exp, double &value )
{
	stack <STATUS> status;
	stack <char>   symbol;
	stack <double> data;
	int      mode = 0;
	int      status_val;
	int      r_flags;
	int      index;
	int      k;
	double   s = 0.0;
	double   m = 0.0;
	int      n = 0;
	bool     num_flags = false;
	bool     dot_flags  = false;
	exp += "#";
	symbol.push('#');
	status.push(0);
	//消去空格
    for (string::iterator it=exp.begin(); it != exp.end(); )
	{
		if(*it == ' ')     exp.erase( it );
		else               ++it;
	}
    //计算
	for(string::size_type ix =0; ix < exp.size(); ix++)
	{
		switch(exp[ix])
		{
		case '.':  if(dot_flags) return 0;
				   else dot_flags = true; 
		case '0': 
		case '1': 
		case '2': 
		case '3': 
		case '4': 
		case '5': 
		case '6': 
		case '7': 
		case '8': 
		case '9':  	
		if(exp[ix] == '.' ) 
			if(num_flags)	continue;
			else            return 0;
		else if(dot_flags && num_flags)
		{ 
			m = m *10 + (exp[ix] -'0');
			n++;  //
			if(exp[ix +1] < '0' || exp[ix+1] >'9')
			{
			dot_flags = false;
			num_flags = false;
			s += m /pow(10.0, n);
			n = 0;
			m = 0.0;
			index =4; 
			break; 
			}
			else continue;
		}
		else{	
			num_flags = true;
			s= s*10 +exp[ix] - '0'; 
			if((exp[ix +1]<'0' || exp[ix+1]>'9') && exp[ix+1] != '.')
			{
			dot_flags = false;
			num_flags = false;
			index =4; 
			break;
			}
			else  continue;
		}
		case '+': 
		case '-':  index =0; break;
		case '*':  
		case '/':  index =1; break;
		case '(':  index =2; break;
		case ')':  index =3; break;
		case '#':  index =5; break;
		default:    return 0;
		}
		
L:	
	k = status.top();
	if (ACTION[k][index].size() == 2)
	{
		if(ACTION[k][index][0] == 'S')    
		{mode = MOVEIN; status_val = ACTION[k][index][1] - '0';}
        else                              
		{mode = REDUCE; r_flags = ACTION[k][index][1] - '0';}
	}
	else if(ACTION[k][index].size() == 3)
	{
		 mode = ACCEPT;
	}
	else mode = ERROR;

	switch(mode)
	{
	case REDUCE:    //规约
		Reduction(symbol, data, status, r_flags);
		goto  L;
		break;

	case MOVEIN:    //移进
	    status.push(status_val);
		if(index == 4)
		{
         	data.push(s);
	    	s = 0.0;
		}
		else
		symbol.push(exp[ix]); 
		break;

	case ACCEPT:   //接受
		value = data.empty() ? 0 : data.top();
		break;

	default:       //报错	
		return 0;
	}
	}
	return  1;
}