arithmeticslr1.cpp

四则算术运算实现,采用的是SLR1文法包括号+,-,*,/,括号,

/*
 *	this program is to calculate the arithmetic expression using SLR1
 *
 */

#include <iostream>
#include <string>
#include <stack>
#include <assert.h>
#include <float.h>

using namespace std;

typedef double	VALUE;

const int NumV = 11;
const int NumVT = 8;
const int NumStates = 14;
const double ERRORNUM = DBL_MAX * -1;

struct genexp
{
	char s;
	int len;
};

struct genexp GenExps[7] = {	{ 'S', 1 }, // S'->E
				{ 'E', 3 }, // E->E+T|E-T
				{ 'E', 1 }, // E->T
				{ 'T', 3 }, // T->T*F|T/F
				{ 'T', 1 }, // T->F
				{ 'F', 3 }, // F->(E)
				{ 'F', 1 }, // F->i
};

enum Actions { ERR, NEXT, SUM, ACC };

//	procedure of calculating the arithmetic expression
VALUE parse( string exp );

// get action value
int action( int state, char sym );

// get goto value
int go( int state, char sym );

// get next symbol
char NextSymbol( string exp, string::iterator & it, VALUE & value );

//	map the charactor to index
unsigned char hash( unsigned char ch );

void main()
{
	string exp;
	const int BUFFER_SIZE = 100;
	char buffer[BUFFER_SIZE];
	VALUE result;

//	freopen( "input.txt", "r", stdin );

	while (1)
	{
		cout << "please input a arithmetic expression:" << endl;
		cin.getline( buffer, BUFFER_SIZE );
		if ( strlen( buffer ) == 0 )
		{
			break;
		}
		else
		{
			exp = buffer;
			if ( ( result = parse( exp ) ) != ERRORNUM )
				cout << "The value of the expression is: " << result << endl;
			else 
				cout << "Expression error!" << endl;
		}
	}
}

//	function of processing with any regualar arithmetic expression
VALUE parse( string exp )
{
	stack<int>	states;		// stack to save states of every step
	stack<char>	symbols;	// stack to save symbols of every step
	stack<VALUE>	data;		// stack to save datas in the expression
	
	exp = "#" + exp + "#";
	VALUE	data_elem = 0;

	string::iterator	it = exp.begin();
	symbols.push( *it );	// original symbol '#'
	it++;

	states.push( 0 );	// original state

	char sym;

	sym = NextSymbol( exp , it, data_elem );
	while ( 1 )	
	{
		if ( hash(sym) >= 0 )	
		{
			switch ( action( states.top(), sym ) )
			{
			case ERR:
				return ERRORNUM;
				break;
			case NEXT:
				symbols.push( sym );
				states.push( go( states.top(), sym ) );
				if ( sym == 'i' )
					data.push( data_elem );
				sym = NextSymbol( exp , it, data_elem );
				break;
			case SUM:
				if ( go( states.top(), sym ) < 0 )
				{
					return ERRORNUM;
				}
				else if (  GenExps[ go( states.top(), sym ) ].len == 1 )
				{
					symbols.top() = GenExps[ go( states.top(), sym ) ].s;
					states.pop();
					states.push( go( states.top(), symbols.top() ) );
				}	
				else
				{
					symbols.pop();
					char oper = symbols.top();
					symbols.pop();
					symbols.top()= GenExps[ go( states.top(), sym ) ].s;
					states.pop();
					states.pop();
					states.pop();
					states.push( go( states.top(), symbols.top() ) );	

					VALUE second = data.top();
					data.pop();
					switch ( oper )
					{
					case '+':
						data.top() += second;
						break;
					case '-':
						data.top() -= second;
						break;
					case '*':
						data.top() *= second;
						break;
					case '/':
						if ( ! second )
							return ERRORNUM;
						data.top() /= second;
						break;
					default:
						data.push( second );
					}
				}
				break;
			case ACC:
				return data.top();
				break;
			}
		}
		else // invalid character
		{
			return ERRORNUM;
		}

	}	
}

int action( int state, char sym )
{
	//	action table
	static	char action[NumStates][NumVT] = {
		/*	i	+	-	*	/	(	)	#	 */
		{	NEXT,	ERR,	ERR,	ERR,	ERR,	NEXT,	ERR,	ERR	}, //	0
		{	ERR,	NEXT,	NEXT,	ERR,	ERR,	ERR,	ERR,	ACC	}, //	1
		{	ERR,	SUM,	SUM,	NEXT,	NEXT,	ERR,	SUM,	SUM	}, //	2
		{	ERR,	SUM,	SUM,	SUM,	SUM,	ERR,	SUM,	SUM	}, //	3
		{	NEXT,	ERR,	ERR,	ERR,	ERR,	NEXT,	ERR,	ERR	}, //	4
		{	ERR,	SUM,	SUM,	SUM,	SUM,	ERR,	SUM,	SUM	}, //	5
		{	NEXT,	ERR,	ERR,	ERR,	ERR,	NEXT,	ERR,	ERR	}, //	6
		{	NEXT,	ERR,	ERR,	ERR,	ERR,	NEXT,	ERR,	ERR	}, //	7
		{	ERR,	NEXT,	NEXT,	ERR,	ERR,	ERR,	NEXT,	ERR	}, //	8
		{	ERR,	SUM,	SUM,	NEXT,	NEXT,	ERR,	SUM,	SUM	}, //	9
		{	ERR,	SUM,	SUM,	SUM,	SUM,	ERR,	SUM,	SUM	}, //	10
		{	ERR,	SUM,	SUM,	SUM,	SUM,	ERR,	SUM,	SUM	}, //	11
		{	NEXT,	ERR,	ERR,	ERR,	ERR,	NEXT,	ERR,	ERR	}, //	12
		{	NEXT,	ERR,	ERR,	ERR,	ERR,	NEXT,	ERR,	ERR	}, //	13
	};
	return action[state][ hash(sym) ];
}

int go( int state, char sym )
{
	//	goto table
	static	char go[NumStates][NumV] = {
		/*	i	+	-	*	/	(	)	#	E	T	F	 */
		{	5,	-1,	-1,	-1,	-1,	4,	-1,	-1,	1,	2,	3	}, //	0
		{	-1,	6,	12,	-1,	-1,	-1,	-1,	-1,	-1,	-1,	-1	}, //	1
		{	-1,	2,	2,	7,	13,	-1,	2,	2,	-1,	-1,	-1	}, //	2
		{	-1,	4,	4,	4,	4,	-1,	4,	4,	-1,	-1,	-1	}, //	3
		{	5,	-1,	-1,	-1,	-1,	4,	-1,	-1,	8,	2,	3	}, //	4
		{	-1,	6,	6,	6,	6,	-1,	6,	6,	-1,	-1,	-1	}, //	5
		{	5,	-1,	-1,	-1,	-1,	4,	-1,	-1,	-1,	9,	3	}, //	6
		{	5,	-1,	-1,	-1,	-1,	4,	-1,	-1,	-1,	-1,	10	}, //	7
		{	-1,	6,	12,	-1,	-1,	-1,	11,	-1,	-1,	-1,	-1	}, //	8
		{	-1,	1,	1,	7,	13,	-1,	1,	1,	-1,	-1,	-1	}, //	9
		{	-1,	3,	3,	3,	3,	-1,	3,	3,	-1,	-1,	-1	}, //	10
		{	-1,	5,	5,	5,	5,	-1,	5,	5,	-1,	-1,	-1	}, //	11
		{	5,	-1,	-1,	-1,	-1,	4,	-1,	-1,	-1,	9,	3	}, //	12
		{	5,	-1,	-1,	-1,	-1,	4,	-1,	-1,	-1,	-1,	10	}, //	13

	};
	return go[state][ hash(sym) ];
}

unsigned char hash( unsigned char ch )
{
	unsigned int x;
	switch ( ch )
	{
	case 'i':
		x = 0;
		break;
	case '+':
		x = 1;
		break;
	case '-':
		x = 2;
		break;
	case '*':
		x = 3;
		break;
	case '/':
		x = 4;
		break;
	case '(':
		x = 5;
		break;
	case ')':
		x = 6;
		break;
	case '#':
		x = 7;
		break;
	case 'E':
		x = 8;
		break;
	case 'T':
		x = 9;
		break;
	case 'F':
		x = 10;
		break;
	default:
		x = -1;
	}
	return x;
}

char NextSymbol( string exp, string::iterator & it, VALUE & value )
{
	VALUE tmp = 0;
	int todiv = 1;
	bool havepoint = 0;
	while ( it != exp.end() )
	{
		switch ( *it )
		{
		case '+':
		case '-':
		case '*':
		case '/':
		case '(':
		case ')':
		case '#':
			if ( tmp )
			{
				value = tmp / todiv;
				return 'i';
			}
			else
				return *it++;
		default:
			if ( *it >= '0' && *it <= '9' || *it == '.' )
			{
				if ( *it == '.' )
				{
					if ( havepoint )
						return 0;
					else
						havepoint = 1;
				}
				else
				{
					tmp = tmp * 10 + *it - '0';
					if ( havepoint )
						todiv *= 10;
				}
				it++;
			}
			else 
				return 0;
		}
	}
	return 0;
}