表达式求值

一、程序思路

1. 问题分析：

表达式是由运算对象、运算符和圆括号组成的式子。在这个程序中只讨论简单的算术运算。为了实现运算符的优先运算，用两个栈分别存储表达式：
OPND：运算对象栈，用来存储运算对象和运算结果；
OPTR：运算符栈，用来存储运算符；

2. 算法思想：

规定@为表达式的定界符，输入的表达式以@为结束标志

（1）将栈OPND初始化为空，OPTR初始化为表达式的定界符@；

（2）依次读入表达式的每个字符，进行如下操作，直到读到@且OPTR栈的栈顶元素为@：

若当前字符是操作数，则进OPND栈，继续读下一个字符；

若当前字符是运算符，且比OPND的栈顶运算符的优先级高，则进OPTR栈，继续读入下一个字符；

若当前字符是运算符，且比OPND的栈顶运算符的优先级低，则从OPTR栈弹出一个运算符，从OPND栈弹出两个操作数，进行运算，并让运算结果进栈OPND，继续处理当前字符；

若当前字符是运算符，且与OPND的栈顶运算符的优先级相等，则从弹出OPTR栈的栈顶运算符，继续读入下一个字符；

（3）输出OPND的栈顶元素（即表达式的运算结果）。

#二、代码实现：

1、用数组prcd表示各运算符之间的优先级关系

const char prcd[7][7] = {'>', '>', '<', '<', '<', '>', '>',
					   '>', '>', '<',	'<', '<', '>', '>',
					   '>', '>', '>', '>', '<', '>', '>',
					   '>', '>', '>', '>', '<', '>', '>',
					   '<', '<', '<', '<', '<', '=', ' ',	
					   '>', '>', '>', '>', ' ', '>', '>',
				   	   '<', '<', '<', '<', '<', ' ', '='};

2、函数PtrToInt

将运算符与它在数组中的下标相关联，使得利用数组prcd来比较栈顶运算符与当前运算符之间的优先级关系。

int PtrToInt(char c)
{
	if('+' == c)	return 0;
	if('-' == c)	return 1;
	if('*' == c)	return 2;
	if('/' == c)	return 3;
	if('(' == c)	return 4;
	if(')' == c)	return 5;
	if('@' == c)	return 6;
	else
	{
		cerr<<"输入的运算符不合法！"<<endl;
				exit(1);
	}
}

3、函数Operater

用来计算left oper right这个式子的值，并返回。

float Operater(float left, char oper, float right)
{
	switch(oper)
	{
		case '+':
			{
				return left + right;
				break;
			}
		case '-':
			{
				return left - right;
				break;
			}
		case '*':
			{
				return left * right;
				break;
			}
		case '/':
			{
				if(0 == right)
				{
					cerr<<"除数不能为0！"<<endl;
					exit(1);
				}
				return left / right;
				break;
			}
		default:
			{
				cerr<<"输入的运算符不合法！！"<<endl;
				exit(1);
			}
	}
}

4、函数Calculate

用来计算表达式的值，用两个栈OPND和OPTR分别存放运算对象和运算符。依次读入表达式的字符，进行操作数和运算符的判断，并进入各自的栈。根据运算符的优先级，进行计算，最后得出结果，返回表达式的值。

float Calculate ()
{
	SeqStack<float, MaxSize> OPND;			//运算对象栈
	SeqStack<char, MaxSize> OPTR;			//运算符栈
	OPTR.Push('@');							//初始化运算符栈
	float left, right;						//左操作数，右操作数
	char oper;								//双目运算符
	cout<<"请输入要计算的表达式："<<endl;	
	char ch;	
	ch = getchar();
	
	while(ch != '@' || OPTR.GetTop() != '@')
	{
		if(ch >= '0' && ch <= '9')
		{
			OPND.Push(ch - '0');
			ch = getchar();
		}
		else
		{
			switch(prcd[PtrToInt(OPTR.GetTop())][PtrToInt(ch)])
			{
				case '<':
					{
						OPTR.Push(ch);
						ch = getchar();
						break;
					}
				case '>':
					{
						oper = OPTR.Pop();
						right = OPND.Pop();
						left = OPND.Pop();
						OPND.Push(Operater(left, oper, right));
						break;
					}
				case '=':
					{
						oper = OPTR.Pop();
						ch = getchar();
						break;
					}
			}
		}
	}
	return OPND.GetTop();
}

5、测试结果

int main()
{
	
	double result = Calcu();
	cout << result << endl;
	return 0;
}

简单的案例：
此处输入图片的描述

此处输入图片的描述
错误的案例：

#三、总结
基本的实现了算数操作，但有关功能还待后续版本。

一、 程序思路