NYOJ 35 表达式求值（栈）

现在的位置: 首页 > 综合 > 正文

NYOJ 35 表达式求值（栈）

2013年08月14日 ⁄ 综合 ⁄ 共 6456字 ⁄ 字号小中大 ⁄ 评论关闭

这些函数中都有“重复”的，因为操作数(OPND)栈用double，操作符(OPTR)栈用char。C++中的模板可以解决这个问题吗？

这是对着书写的：

#include <iostream>
using namespace std;

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 100

char Precede_Matrix[7][7] = 
{
	{'>', '>', '<', '<', '<', '>', '>',},
	{'>', '>', '<', '<', '<', '>', '>',},
	{'>', '>', '>', '>', '<', '>', '>',},
	{'>', '>', '>', '>', '<', '>', '>',},
	{'<', '<', '<', '<', '<', '=', '0',},
	{'>', '>', '>', '>', '0', '>', '>',},
	{'<', '<', '<', '<', '<', '0', '=',}
};

char Precede ( char a, char b )
{
	int i = 0;
	int j = 0;
	switch (a)
	{
	case '+' : i = a - '+'; break;
	case '-' : i = a - '-' + 1; break;
	case '*' : i = a - '*' + 2; break;
	case '/' : i = a - '/' + 3; break;
	case '(' : i = a - '(' + 4; break;
	case ')' : i = a - ')' + 5; break;
	case '#' : i = a - '#' + 6; break;
	default : cout << "Error1!" << endl;
	}
	switch (b)
	{
	case '+' : j = b - '+'; break;
	case '-' : j = b - '-' + 1; break;
	case '*' : j = b - '*' + 2; break;
	case '/' : j = b - '/' + 3; break;
	case '(' : j = b - '(' + 4; break;
	case ')' : j = b - ')' + 5; break;
	case '#' : j = b - '#' + 6; break;
	default : cout << "Error2!" << endl;
	}
	char c = Precede_Matrix[i][j];
	return c;
}

int Operate(int a, char oper, int b)
{
	switch (oper)
	{
	case '+': return a + b;
	case '-': return a - b;
	case '*': return a * b;
	case '/': return a / b;
	default: cout << "Error3!" << endl; return 0;
	}
}

struct stack_char
{
	char *base;
	char *top;
	int stacksize;
}OPTR;

struct stack_int
{
	int *base;
	int *top;
	int stacksize;
}OPND;	// 两位数的只能用int来存？

void InitStack(struct stack_char &S)
{
	S.base = (char *)malloc( STACK_INIT_SIZE * sizeof(char) );
	if(!S.base)
		cout << "Overflow1!" << endl;
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;	
}

void InitStack(stack_int &S)
{
	S.base = (int *)malloc( STACK_INIT_SIZE * sizeof(int) );
	if(!S.base)
		cout << "Overflow2!" << endl;
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;	
}

void Push(stack_char &S, char e)
{
	if(S.top - S.base >= S.stacksize)	// 判满
	{
		S.base = (char *)realloc( S.base,
			(S.stacksize + STACKINCREMENT) * sizeof(char) );
		if(!S.base)
			cout << "Overflow3!" << endl;
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	* S.top++ = e;
}

void Push(stack_int &S, int e)
{
	if(S.top - S.base >= S.stacksize)	// 判满
	{
		S.base = (int *)realloc( S.base, 
			(S.stacksize + STACKINCREMENT) * sizeof(int) );
		if(!S.base)
			cout << "Overflow4!" << endl;
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	* S.top++ = e;
}

void Pop (stack_char &S, char &e)
{
	if(S.top == S.base)					// 判空
		cout << "Error4!" << endl;
	e = * --S.top;
}

void Pop (stack_int &S, int &e)
{
	if(S.top == S.base)					// 判空
		cout << "Error5!" << endl;
	e = * --S.top;
}

char GetTop(stack_char S)
{
	if (S.top == S.base)				// 判空
		cout << "Error6!" << endl;
	return *(S.top - 1);
}

int GetTop(stack_int S)
{
	if (S.top == S.base)				// 判空
		cout << "Error7!" << endl;
	return *(S.top - 1);
}

int EvaluateExpression()
{
	int a;
	int b;
	char x;
	char theta;
	InitStack(OPTR);
	Push(OPTR, '#');
	InitStack(OPND);
	char c = getchar();					// 输入若是数字，只能是个位数
	while ( !(c == '#' && GetTop(OPTR) == '#') )
	{
		if ( '0' <= c && c <= '9' )		// c is operand
		{
			c -= '0';
			Push(OPND, c);
			c = getchar();
		}
		else							// c is operator or delimiter
		{
			switch (Precede (GetTop(OPTR), c))
			{
			case '<':
				Push(OPTR, c);
				c = getchar();
				break;
			case '=':
				Pop(OPTR, x);
				c = getchar();
				break;
			case '>':
				Pop(OPTR, theta);
				Pop(OPND, b);
				Pop(OPND, a);
				Push(OPND, Operate(a, theta, b));
				break;
			default: cout << "Error8!" << endl;
			}
		}
	}
	//  OPTR栈的栈顶元素和当前读入的字符均为“#”
	//  即“#”=“#”时整个表达式求值完毕
	int result = GetTop(OPND);	
	free(OPTR.base);
	free(OPND.base);
	return result;	//	要在释放前保留下结果
}							

int main()
{	
	cout << EvaluateExpression() << endl;
	
	return 0;
}

NYOJ上该题的标程：

 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char str[1005];
int start;
char s[50],ss[50];int i,j;
double Term();double Expression();double Factor();
double Term()
{
    double f=Factor(),t;
    --start;
    if(str[start]=='*')
    {
        t=Term();
        return t*f;
    }
    else if(str[start]=='/')
    {
        t=Term();
        return t/f;
    }
    else {++start;return f;}
}
double Expression()
{
    double t=Term(),e;
    --start;
    if(str[start]=='+')
    {
        e=Expression();
        return e+t;
    }
    else if(str[start]=='-')
    {
        e=Expression();
        return e-t;
    }
    else {++start;return t;}
}
double Factor()
{
    --start;
    double ret;
    if(str[start]==')')
    {
        ret=Expression();
        --start;
        return ret;
    }
    else
	{
		i=0;
		memset(ss,0,sizeof(ss));
		while((str[start]>='0'&&str[start]<='9')||str[start]=='.')
			s[i++]=str[start--];
		++start;
		for(j=0;j<i;j++)
		{
			ss[j]=s[i-1-j];
		}
		return atof(ss);
	}
}
int main()
{
	//freopen("1.txt","r",stdin);
	int n;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s",str);
		start=strlen(str)-1;
		printf("%.2lf\n",Expression());
	}
}

2012/5/17 更新：

终于用模板解决了那个问题

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;

#define STACK_INIT_SIZE 1024
#define STACKINCREMENT 30

char Precede_Matrix[7][7] = 
{
	{'>', '>', '<', '<', '<', '>', '>',},
	{'>', '>', '<', '<', '<', '>', '>',},
	{'>', '>', '>', '>', '<', '>', '>',},
	{'>', '>', '>', '>', '<', '>', '>',},
	{'<', '<', '<', '<', '<', '=', '0',},
	{'>', '>', '>', '>', '0', '>', '>',},
	{'<', '<', '<', '<', '<', '0', '=',}
};

char Precede ( char a, char b )
{
	int i = 0;
	int j = 0;
	switch (a)
	{
	case '+' : i = 0; break;
	case '-' : i = 1; break;
	case '*' : i = 2; break;
	case '/' : i = 3; break;
	case '(' : i = 4; break;
	case ')' : i = 5; break;
	case '#' : i = 6; break;
	default : cout << "Error1!" << endl;
	}
	switch (b)
	{
	case '+' : j = 0; break;
	case '-' : j = 1; break;
	case '*' : j = 2; break;
	case '/' : j = 3; break;
	case '(' : j = 4; break;
	case ')' : j = 5; break;
	case '#' : j = 6; break;
	default : cout << "Error2!" << endl;
	}

	return ( Precede_Matrix[i][j] );
}

double Operate(double a, char oper, double b)
{
	switch (oper)
	{
	case '+': return a + b;
	case '-': return a - b;
	case '*': return a * b;
	case '/': return a / b;
	default: cout << "Error3!" << endl; return -1;
	}
}

struct stack_char
{
	char *base;
	char *top;
	int stacksize;
};

struct stack_double
{
	double *base;
	double *top;
	int stacksize;
};  // 计算结果可能是两位数，只能用double，不能用char来存？

template <class T2, class T1>
void InitStack(T1 &S)
{
	S.base = (T2 *)malloc( STACK_INIT_SIZE * sizeof(T2) );
	if(!S.base)
		cout << "Overflow2!" << endl;
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;  
}

template <class T1, class T2>
void Push(T1 &S, T2 e)
{
	if(S.top - S.base >= S.stacksize)    // 判满
	{
		S.base = (T2 *)realloc( S.base,
			(S.stacksize + STACKINCREMENT) * sizeof(T2) );
		if(!S.base)
			cout << "Overflow3!" << endl;
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
}

template <class T1, class T2>
void Pop (T1 &S, T2 &e)
{
	if(S.top == S.base)                 // 判空
		cout << "Error5!" << endl;
	e = *--S.top;
}

template <class T2, class T1>
T2 GetTop(T1 S)
{
	if (S.top == S.base)                // 判空
		cout << "Error6!" << endl;
	return *(S.top - 1);
}

bool IsOperand(char c)
{
	if( ('0' <= c && c <= '9') || c == '.' )	//	c是数字或小数点
		return true;
	else
		return false;
}

int main(void)
{
	string str;
	while (cin >> str) {
		str.push_back('#');						//  最后是#（结束标志）
		double a;
		double b;
		char x;
		char theta;
		stack_char OPTR;
		InitStack<char> (OPTR);
		Push(OPTR, '#');
		stack_double OPND;
		InitStack<double> (OPND);
		int i = 0;
		char c = str[i++];
		double operand = 0;
		while ( !(c == '#' && GetTop<char> (OPTR) == '#') )
		{
			if ( IsOperand(c) )					// c is operand
			{
				operand = atof( &str[i - 1] );	//	把从c开头的数转化成double
				Push(OPND, operand);
				while( IsOperand(str[i]) )
					i++;
				c = str[i++];
			}			
			else                            // c is operator or delimiter
			{
				switch (Precede (GetTop<char> (OPTR), c))
				{

				case '<':
					Push(OPTR, c);
					c = str[i++];
					break;

				case '=':
					Pop(OPTR, x);
					c = str[i++];
					break;

				case '>':
					Pop(OPTR, theta);
					Pop(OPND, b);
					Pop(OPND, a);
					Push(OPND, Operate(a, theta, b));
					break;

				default:
					cout << "Error8!" << endl;
					break;
				}
			}       
		}
		//  OPTR栈的栈顶元素和当前读入的字符均为“#”
		//  即“#”=“#”时整个表达式求值完毕
		cout << GetTop<double> (OPND) << endl;

		free(OPTR.base);
		free(OPND.base);
	}

	return 0;
}

同时功能上改进了，欢迎体验！

【上篇】等待对话框
【下篇】在SQL Server中获取Excel文件中所有Sheet工作表的名称

作者: surefire

该日志由 surefire 于11年前发表在综合分类下，最后更新于 2013年08月14日.
转载请注明: NYOJ 35 表达式求值（栈） | 学步园 +复制链接

抱歉!评论已关闭.

学步园

NYOJ 35 表达式求值（栈）

作者: surefire

书签

最新文章New

本站推荐

返回首页