expression.cpp

用栈实现中缀表达式求值的问题。同时实现了逆波兰表达式的问题。

#include <iostream.h>
#include <string.h>
#include <math.h>
#include "SqStack.h"

#define MAX 50

double Operate(double a, char theta, double b)
{//计算(a theta b)
	double value;

	switch(theta)
	{
	case '+':  value = a + b;  break;
	case '-':  value = a - b;  break;
	case '*':  value = a * b;  break;
	case '/':  value = a / b;  break;
	case '^':  value = pow(a, b);  break;
	}
	
	return value;
}
////////////////////////////////////////////////////////////////////////////////////

char Precede(char theta1, char theta2)
{//判断运算符theta1、theta2的优先权
	int i, ind[2];
	char ch[2];
	char re[8][8] = {'>','>','<','<','<','<','>','>',
		             '>','>','<','<','<','<','>','>',
					 '>','>','>','>','<','<','>','>',
					 '>','>','>','>','<','<','>','>',
					 '>','>','>','>','>','<','>','>',
					 '<','<','<','<','<','<','=','!',
					 '>','>','>','>','>','!','>','>',
					 '<','<','<','<','<','<','!','='};
	ch[0] = theta1;
	ch[1] = theta2;
	for(i=0; i<=1; ++i)
	{
		switch(ch[i])
		{
		case '+':  ind[i] = 0;	break;
		case '-':  ind[i] = 1;	break;
		case '*':  ind[i] = 2;	break;
		case '/':  ind[i] = 3;	break;
		case '^':  ind[i] = 4;	break;
		case '(':  ind[i] = 5;	break;
		case ')':  ind[i] = 6;	break;
		case '#':  ind[i] = 7;	break;
		default:   return '!';
		}
	}
	
	return re[ind[0]][ind[1]];
}
////////////////////////////////////////////////////////////////////////////////////

void Porland(char *expression)
{
	Stack_Char OPTR;
	double num;
	int i, k;
	char *p, strnum[MAX], c;
	InitStack(OPTR);
	Push(OPTR, '#');

	p = expression;
	
	strcat(expression, "#");
	while(*p!='#' || GetTop(OPTR)!='#')
	{
		if(*p>='0' && *p<='9')
		{//读到数字
			for(k=1; p[k]>='0' && p[k]<='9'; ++k);
			for(i=0; i<k; ++i)
			{
				strnum[i] = p[i];
			}
			strnum[i] = '\0';
			num = atof(strnum);
			cout<<num<<"  ";
			p += k;
		}
		else
		{//读到运算符
			switch(Precede(GetTop(OPTR), *p))
			{
			case '<':   //栈顶元素优先权低
				Push(OPTR, *p); 
			    p += 1;
	    		break;
			case '=':   //脱括号
				Pop(OPTR, c);
				p += 1;
				break;
			case '>':   //栈顶元素优先权高
				Pop(OPTR, c);
				cout<<c<<"   ";
				break;
			default:
				cout<<"表达式有错，不能转化成逆波兰表达式！\n";
				DestroyStack(OPTR);
				return;
			}
		}
	}
	cout<<'\n';
	
	DestroyStack(OPTR);
}

///////////////////////////////////////////////////////////////////////////////////

Status EvaluateExpression(char *expression, double &value)
{//表达式求值
	Stack_Char OPTR;
	Stack_Double OPND;
	double num, a, b;
	int i, k;
	char *p, strnum[MAX], c, theta;

	InitStack(OPTR);
	Push(OPTR, '#');
	InitStack(OPND);
	
	strcat(expression, "#");
	
	p = expression;

	while(*p!='#' || GetTop(OPTR)!='#')
	{
		if(*p>='0' && *p<='9')
		{//读到数字
			for(k=1; p[k]>='0' && p[k]<='9'; ++k);
			for(i=0; i<k; ++i)
			{
				strnum[i] = p[i];
			}
			strnum[i] = '\0';
			num = atof(strnum);
			Push(OPND, num);
			p += k;
		}
		else
		{//读到运算符
			switch(Precede(GetTop(OPTR), *p))
			{
			case '<':   //栈顶元素优先权低
				Push(OPTR, *p); 
			    p += 1;
	    		break;
			case '=':   //脱括号并接收下一字符
				Pop(OPTR, c);
				p += 1;
				break;
			case '>':   //退栈并将运算结果入栈
				Pop(OPTR, theta);
			    Pop(OPND, b);
				Pop(OPND, a);
				Push(OPND, Operate(a, theta, b));
				break;
			default:
				return ERROR;
			}
		}
	}
	
	value = GetTop(OPND);

	DestroyStack(OPTR);
	DestroyStack(OPND); 

	return OK;
}
//////////////////////////////////////////////////////////////////////////

void main(void)
{
	char expression[MAX];
	double value;
	
	cout<<"请输入表达式：\n";
	cin.getline(expression, MAX);
	
	Porland(expression);    //输出逆波兰表达式

	if(EvaluateExpression(expression, value))
		cout<<value<<'\n';
	else
		cout<<"表达式有错，不能计算！\n";
}