_compute.cpp

计算器

//             _____________________________________
//            |                                     |
//            |               文件描述              |
// ___________|_____________________________________|___________
//
// 文件名：_compute.cpp
// 作者：阿卓
// 内容：简单表达式求值C++程序代码段。
// 声明：本文件及其相关文档内容可以自由使用、修改和传播，并可用
//       于任何商业和非商业目的。对于使用本文件及其相关文档内容
//       而产生的任何后果，作者概不负责。
//
// 技术要点之一：
//     算符优先矩阵的使用。
//
// 技术要点之二：
//     堆栈的操作。
//
// 当前版本：v1.1
// 最后更新日期：11/8/2001
//
// 版本历史：
// v1.0
//     算法初步成型，能够计算整数和浮点数的加减乘除，能够进行带
//     括号的四则运算，可以判断括号不配对核语法错误等。
// v1.1
//     修正了一些BUG，加入了详细的注释描述。
//
// _______________________文件描述结束__________________________


// 这是MFC程序需要的头文件，以支持预编译头文件
#include "stdafx.h"

#define MAXNUM 30
#define MAXLEN 80
#define GET(x) if((x = get(a)) == -1) return (symbolerr = 1);

// 定义算符的堆栈结构
typedef struct {
	char	stack[MAXNUM];
	int		top;
}optrtype;

// 定义操作数的堆栈结构
typedef struct {
	double	stack[MAXNUM];
	int		top;
}opndtype;

static double	f = 0;
static char		l = '#';
static int		j = 0;
static int		syntaxerr = 0, symbolerr = 0, emptyflag = 0, overflow = 0;

//      _________
// ____|  get()  |______________________________________________
// 功能：内部函数，从输入字符串析取单词
// 参数详解：
// char a[]
//     存储原输入串的字符数组
// 返回值：
//     -1 - 出现非法符号
//     0 - 解析出一操作数
//     其它 - 返回算符
// _____________________________________________________________
static char get(char a[])
{
	char	c, c1;
	double	t = 0.0, s = 0.0;

	c = a[j ++];
	// 如果是算符
	if(c == '+' || c == '-' || c == '*' || c == '/' ||
		c == '(' || c == ')' || c == '#') {
		if(c == '-' && l != ')' && l != 0) {
			c1 = get(a);
			// 如果是求负运算符,再读后一个单词
			if(c1 == -1)
				return -1;
			if(c1 == 0) {
				// 操作数求负
				f *= -1;
				return (l = 0);
			} else {
				j --;
				// 返回求负运算符
				return (l = '!');
			}
		} else {
			return (l = c);
		}
	}else if(c >= '0' &&  c <= '9') { // 是操作数则提取
		// 处理整数部分
		while(c >= '0' && c <= '9') {
			t = t * 10.0 + c - '0';
			c = a[j ++];
			s = t;
		}
		// 如果有小数部分
		if(c == '.') {
			t = 1.0;
			c = a[j ++];
			// 处理小数部分
			while(c >= '0' && c <= '9') {
				t *= 0.1;
				s += t * (c - '0');
				c = a[j ++];
			}
		}
		j --;

		// 提取出的操作数存于f
		f = s;

		// 返回操作数标志
		return (l = 0);
	} else {
		// 非法字符返回出错代码
		return -1;
	}
}
// _____End of get()____________________________________________

//      _____________
// ____|  operate()  |__________________________________________
// 功能：内部函数，对两个操作数运算
// 参数详解：
// double a
//     第一个操作数，双精度型
// char t
//     运算符，字符型
// double b
//     第一个操作数，双精度型
// 返回值：
//     运算结果，双精度型
// _____________________________________________________________
static double operate(double a, char t, double b)
{
	switch(t) {
	case '+': return (a + b);
	case '-': return (a - b);
	case '*': return (a * b);
	case '/':
		if(b == 0.0 )
			return (overflow = 1);
		else
			return (a / b);
	default:
		return 0.0;
	}
}
// _____End of operate()________________________________________

//      _____________
// ____|  proceed()  |__________________________________________
// 功能：内部函数，比较两个算符的优先级
// 参数详解：
// char x1
//     第一个算符
// char x2
//     第二个算符
// 返回值：
//     -1 - x1 < x2
//      1 - x1 > x2
//      0 - x1 = x2
//     -2 - N/A
// _____________________________________________________________
static int proceed(char x1, char x2)
{
	int		x, y;
	char	t[8] = {'!','+','-','*','/','(',')','#'};
	// 运算符优先级关系表
	int		table[8][8] = {
		{-1,  1,  1,  1,  1, -1,  1,  1},
		{-1,  1,  1, -1, -1, -1,  1,  1},
		{-1,  1,  1, -1, -1, -1,  1,  1},
		{-1,  1,  1,  1,  1, -1,  1,  1},
		{-1,  1,  1,  1,  1, -1,  1,  1},
		{-1, -1, -1, -1, -1, -1,  0, -2},
		{-2,  1,  1,  1,  1, -2,  1,  1},
		{-1, -1, -1, -1, -1, -1, -2,  0}
	};

	for(x = 0; t[x] != x1; x ++);
	for(y = 0; t[y] != x2; y ++);

	return (table[x][y]);
}
// _____End of proceed()________________________________________

//      __________________
// ____|  堆栈操作函数集  |_____________________________________
// 功能：内部函数，操作算符和操作数堆栈的函数集，有初始化、压栈、
//       出栈、取栈顶元素等操作。
// _____________________________________________________________
static void init_optr(optrtype *s)
{
	s -> top = -1;
}

static void init_opnd(opndtype *s)
{
	s -> top = -1;
}

static int pushoptr(optrtype *s, char x)
{
	if(s -> top >= MAXNUM - 1)
		return -1;
	else {
		s -> top ++;
		s -> stack[s -> top] = x;
		return 1;
	}
}

static int pushopnd(opndtype *s, double x)
{
	if(s -> top >= MAXNUM - 1)
		return -1;
	else {
		s -> top ++;
		s -> stack[s -> top] = x;
		return 1;
	}
}

static char gettopoptr(optrtype s)
{
	if(s.top < 0)
		return (emptyflag = 1);
	else
		return (s.stack[s.top]);
}

static double gettopopnd(opndtype s)
{
	if(s.top < 0)
		return (emptyflag = 1);
	else
		return (s.stack[s.top]);
}

static char popoptr(optrtype *s)
{
	if(s -> top < 0)
		return (emptyflag = 1);
	else {
		s -> top --;
		return (s -> stack[s -> top + 1]);
	}
}

static double popopnd(opndtype *s)
{
	if(s -> top < 0)
		return (emptyflag = 1);
	else {
		s -> top --;
		return (s -> stack[s -> top + 1]);
	}
}
// _____Enf of 堆栈操作函数集___________________________________

//      _____________
// ____|  execute()  |__________________________________________
// 功能：核心执行函数，总控分析输入串和执行对表达式的求值
// 参数详解：
// char a[]
//     存储原输入串的字符数组
// 返回值：
//     运算结果，双精度型
// _____________________________________________________________
double execute(char a[]) /* 对输入表达式运算且返回结果 */
{
	char		x, theta;
	double		r, x1, x2;
	optrtype	optr, *s;
	opndtype	opnd, *p;

	j = 0;
	symbolerr = 0;
	emptyflag = 0;
	overflow = 0;
	syntaxerr = 0;

	s = &optr;
	p = &opnd;
	// 栈初始化
	init_optr(s);
	pushoptr(s, '#');
	init_opnd(p);
	// 提取第一个单词
	GET(x);
	while(!(x == '#' && gettopoptr(*s) == '#')) {
		if(x == 0) {
			// 是操作数入栈,读取下一个单词
			pushopnd(p, f);
			GET(x);
		} else {
			switch(proceed(gettopoptr(*s), x)) {
			// 栈顶元素优先级低
			case -1:
				pushoptr(s, x);
				GET(x);
				break;

			// 脱括号并接收下一单词
			case 0:
 				popoptr(s);
				GET(x);
				break;

			// 栈顶元素优先级高
			case 1:
				theta = popoptr(s);
				// 是求负运算符只弹出一个操作数
				if(theta == '!') {
					x2 = popopnd(p) * (- 1.0);
					if(emptyflag == 1)
						return (syntaxerr = 1);
					pushopnd(p, x2);
				} else {
					// 退栈并将结果入栈
					x2 = popopnd(p);
					x1 = popopnd(p);
					if(emptyflag == 1)
						return (syntaxerr = 1);
					r = operate(x1, theta, x2);
					if(overflow)
						return (syntaxerr = 1);
					pushopnd(p, r);
				}
				break;
			case -2:
				return (syntaxerr = 1);
			}
		}
	}
	// 运算结果不是栈顶元素则置错误标志
	if(p -> top != 0)
		return (syntaxerr = 1);
	else
		return (gettopopnd(*p));
}
// _____End of execute()________________________________________

//      ______________
// ____|  geterror()  |_________________________________________
// 功能：错误检查函数
// 参数详解：
// char *error
//     存放错误信息的缓冲区指针，若没有错误，则返回空字符串
// 返回值：无返回值
// _____________________________________________________________
void geterror(char *error)
{
	if(symbolerr)
		strcpy(error, "错误: 出现非法字符.");
	else if(overflow)
		strcpy(error, "错误: 不能以0为除数.");
	else if(syntaxerr || emptyflag)
		strcpy(error, "错误: 语法错误.");
	else
		strcpy(error, "");
}
// _____End of geterror()_______________________________________