高分请教
我碰到了这样的问题，不知该怎样解决：
我需要计算一个字符串形式的数学式子的值，不知道有没有什么好方法，
这个数学式子集成了各种运算。
请各位帮忙
问题点数：100、回复次数：12Top
1 楼MaiCle（原来小日本连畜生都不如）回复于 2003-08-01 22:43:03 得分 0
使用堆栈可以完成。Top
2 楼qqchen79（知秋一叶）回复于 2003-08-01 22:45:57 得分 5
算符优先表达式求值，google搜一下Top
3 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 22:51:48 得分 90
/*
作者介绍：陈硕，男，1982年4月生，现就读于北京师范大学电子系2000级。
通信方法：100875，北京师范大学 电子系1300信箱 陈硕
E - Mail : chenshuo@chenshuo.com ，个人主页：http://www.chenshuo.com
代码的说明在readme.txt中
Version 0.99 beta
*/
#ifndef CALCULATOR_CLASS
#define CALCULATOR_CLASS
#include "stack.h" // include Stack class
#include "queue.h" // include Queue class
#include <math.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <iostream.h>
const int MaxLength_of_Expression = 500; // 表达式的最大长度
const int MaxLength_of_VariableName = 30; // 变量名的最大长度
const int MaxNumber_of_Variable = 15; // 变量的最大个数,需小于 19
enum ERR_TYPE{
ERR_NO_ERROR = 0,
ERR_EXPRESSION_TOO_LONG = 1, // 表达式太长
ERR_MISS_OPERAND = 2, // 缺少操作数
ERR_MISS_OPERATOR = 3, // 缺少操作符
ERR_MISS_LEFT_PARENTHESIS = 4, // 缺左括号
ERR_MISS_RIGHT_PARAENTHESIS = 5, // 缺右括号
ERR_DEVIDE_BY_ZERO = 6, // 除数为零
ERR_UNKNOWN_OPERATOR = 7, // 未知的操作符
ERR_INVALID_OPERATOR = 8, // 非法操作符
ERR_UNKNOWN_ERROR = 9, // 未知的错误
ERR_TOO_MANY_VARIABLES = 10, // 变量个数太多
ERR_VARIABLE_NAME_TOO_LONG = 11 // 变量名太长
};
enum OPTR_TYPE{
OPTR_MINUS = 41, // 负号
OPTR_POSITIVE = 42, // 正号
OPTR_ADD = 21, // 加法
OPTR_SUBTRACT = 22, // 减法
OPTR_MULTIPLY = 23, // 乘法
OPTR_DIVIDE = 24, // 除法
OPTR_POWER = 25, // 乘方
OPTR_LEFT_PARENTHESIS = 20, // 左括号
OPTR_RIGHT_PARENTHESIS = 40 // 右括号
};
inline double cot(double n)
{ // 反正切
return 1.0 / tan(n);
}
/*
int _matherr (struct _exception *a)
{ //数学运算的异常处理，不同的编译器要求不一
a->retval = 100000.0;
return 1;
}
*/
class Calculator
{
private:
struct element {
int type; // 元素类别,是操作数还是操作符由此定
int icp; // 栈外优先级
int isp; // 栈内优先级
double value; // 如果是普通操作数(非变量),此为值
};
Queue<element> PO; // 后缀表达式, 存储在队列中
double Result; // 表达式的运算结果
double Vars[MaxNumber_of_Variable]; // 表达式中各个变量的值存放于此
char VarName[MaxNumber_of_Variable][MaxLength_of_VariableName]; // 各个变量的名字
char Expression[MaxLength_of_Expression]; // 输入的表达式
mutable int ErrorID; // 最近发生的错误的号码
mutable int ErrorLineNo; // 最近发生的错误的行号
int VarCount; // 变量的个数
void Error(int err, int lineno) const { ErrorID = err; ErrorLineNo = lineno; } // 处理错误
// 以下为将输入的表达式转换为中缀表达式的元素序列所用的函数
void Trim(char *); // 整理输入的表达式,除去非法字符
bool IsOperandChar(int) const; // 当前字符是否属于一个操作数
bool IsOperatorChar(int) const; // 当前字符是否属于一个操作符
void GetOperand(int &, char *) const; // 取得一个操作数(纯数字)
bool GetOperator(int &, char *) const; // 取得一个操作符(字母序列或“+-*/^”等)，成功返回true
bool GetUnary(element &, char , int) const; // 单字符非字母操作符对应的属性，成功返回true
bool GetVariable(element &, const char *, int &); // 表达式中出现的变量的属性，成功返回true
bool GetElement(element &, const char *, int &); // 取得字符串buf对应的元素属性，成功返回true
bool Construe_Numeric(element &, int &, int &) const; //
bool Construe_Operator(element &, int &, int &);
void Construe(Queue<element> &); // 将输入表达式整理为元素序列(即中缀表达式)
// 将中缀表达式转换为后缀表达式
void Conversion(Queue<element> &);
double Calculate(element EL, double x, double y) const; // 双目操作符的运算
double Calculate(element EL, double x) const; // 单目操作符的运算
public: //以下为接口
Calculator(void) { Clear(); }
void Clear(void); // 初始化计算器
const char* GetErrorMessage(int errid) const; // 得到错误信息
int GetErrorID(void) const { return ErrorID; } // 返回错误的号码
int GetErrorLineNo(void) const { return ErrorLineNo; } // 返回发生错误的行号
bool Input(char *); // 向计算器输入一个表达式,成功则返回true
int GetNumberOfVariables(void) { return VarCount; } // 返回表达式中的变量个数
const char* Calculator::GetVariableName(int i); // 得到表达式第i个变量的名称
void Assign(double *); // 给变量赋值
bool Compute(void); // 执行计算,成功则返回true
double GetResult(void) { return Result; }// 返回计算结果
void Test(void); // 演示基本的功能
};
#endif // CALCULATOR_CLASSTop
4 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 22:52:12 得分 0
/*
作者介绍：陈硕，男，1982年4月生，现就读于北京师范大学电子系2000级。
通信方法：100875，北京师范大学 电子系1300信箱 陈硕
E - Mail : chenshuo@chenshuo.com ，个人主页：http://www.chenshuo.com
代码的说明在readme.txt中
Version 0.99 beta
*/
#include <stdio.h>
#include "calculator.h"
void Calculator::Clear(void)
{ // 初始化计算器
PO.Clear();
Result = 0;
ErrorID = ERR_NO_ERROR;
VarCount = 0;
Expression[0] = '\0';
for(int i = 0; i < MaxNumber_of_Variable; i++) {
VarName[i][0] = '\0';
Vars[i] = 0.0;
}
}
const char* Calculator::GetErrorMessage(int errid) const
{
static const char *errmsg[] = {"no errors",
"expression too long",
"missing operand",
"missing operator",
"missing left parenthesis",
"missing right paraenthesis",
"devide by zero",
"unknown operator",
"invalid operator",
"unknown error",
"too many variables",
"variable's name too long",
"UNKNOWN ERROR ID!!!"};
if(errid >= 0 && errid < 12)
return errmsg[errid];
else
return errmsg[12];
}
void Calculator::Assign(double *pExtVars)
{ // 将pExtVars所指向数组的值赋给Vars[]
double *pd = Vars;
while(pd < Vars + VarCount)
*pd++ = *pExtVars++;
}
const char* Calculator::GetVariableName(int i)
{
if (i>=0 && i<VarCount) {
return VarName[i];
} else {
return 0;
}
}
void Calculator::Trim(char *buf)
{ //初始化,去除str[]中的非法字符
//char buf[MaxLength_of_Expression];
char charset[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+-*/()^."; //合法的字符
strupr(buf);
int i = 0;
int j = 0;
char ch;
while(ch = buf[i++]) {
if(strchr(charset, ch))
Expression[j++] = ch;
}
Expression[j] = '\0';
}
bool Calculator::IsOperandChar(int i) const
{ //判断是否为操作数字符
char ch, ch0, ch1;
int l = strlen(Expression);
ch = Expression[i];
ch0 = Expression[i==0 ? 0:i-1];
ch1 = Expression[i==l-1 ? i:i+1];
if(isdigit(ch) || ch == '.')
return true;
if(ch == '-'||ch == '+') //判断这个"+"或"-"是不是数字的一部分
if(strchr("+-*/^(", ch0) != 0 && (isdigit(ch1) || ch1 == '.'))
return true;
return false;
}
bool Calculator::IsOperatorChar(int i) const
{ //判断是否为操作符字符
char ch = Expression[i];
if(strchr("+-*/^", ch)!=NULL)
return true;
if(isalpha(ch))
return true;
return false;
}
void Calculator::GetOperand(int &i, char *buf) const
{ //读取完整的操作数
int t = 0;
while(IsOperandChar(i))
buf[t++] = Expression[i++];
buf[t] = '\0';
}
bool Calculator::GetOperator(int &i, char *buf) const
{ //读取完整的操作符 如SIN COS及变量名等
int t = 0;
char ch;
ch = Expression[i];
if(strchr("+-*/^", ch) != 0) { //取单字符的双目操作符
buf[t++]=ch;
i++;
buf[t] = '\0';
return true;
}
//取连续的由字母和数字组成的字符串
while(isalnum(Expression[i])) {
buf[t++] = Expression[i++];
if(t >= MaxLength_of_VariableName) {
Error(ERR_VARIABLE_NAME_TOO_LONG, __LINE__);
return false;
}
}
buf[t] = '\0';
return true;
}
bool Calculator::GetUnary(element &EL, char ch, int rank) const
{ // 处理单字符非字母操作符
if(rank == 1) { // 需要双目操作符
EL.isp = 1; EL.icp = 1;
switch (ch) {
case '+': EL.type = OPTR_ADD; break;
case '-': EL.type = OPTR_SUBTRACT; break;
case '*': EL.type = OPTR_MULTIPLY; EL.isp = EL.icp = 2; break;
case '/': EL.type = OPTR_DIVIDE; EL.isp = EL.icp = 2; break;
case '^': EL.type = OPTR_POWER; EL.isp = 3; EL.icp = 4; break;
default : Error(ERR_UNKNOWN_OPERATOR, __LINE__); return false;
}
return true;
}
if(rank == 0) { // 需要单目操作符
EL.isp = 4; EL.icp = 5;
switch (ch) {
case '+': EL.type = OPTR_POSITIVE; break;
case '-': EL.type = OPTR_MINUS; break;
default : Error(ERR_UNKNOWN_OPERATOR, __LINE__); return false;
}
return true;
}
return false; //Error!
}
bool Calculator::GetVariable(element &EL, const char *buf, int &rank)
{
int j;
for(j = 0; j < VarCount; j++) {//是否为已知变量
if(strcmp(VarName[j], buf) == 0) { //若是变量,则EL为操作数
EL.type = 1 + j;
EL.isp = 0; EL.icp = 0;
rank++; // 操作数的等级为1,累计等级rank自加1
if (rank > 1) {
Error(ERR_MISS_OPERATOR, __LINE__);
return false;
}
return true;
}
}
if (VarCount < MaxNumber_of_Variable) {
strcpy(VarName[VarCount], buf); //添加新变量
EL.type = 1 + j;
EL.isp = 0; EL.icp = 0;
VarCount++;
rank++;
if (rank > 1) {
Error(ERR_MISS_OPERATOR, __LINE__);
return false;
}
return true;
} else {
Error(ERR_TOO_MANY_VARIABLES, __LINE__);
return false;
}
}
bool Calculator::GetElement(element &EL, const char *buf, int &rank)
{ // 得到buf所指的字符串对应的表达式元素的属性
static char *fname[]={"SIN", "COS", "TAN", "SQR", "LOG10",
"LOG", "COT", "ABS", "INT", "ARCSIN", "ARCCOS", "ARCTAN",
"SINH", "COSH", "TANH", "EXP", "SQRT", 0}; //支持的数学函数的名称
int l, j;
char ch;
l = strlen(buf);
ch = buf[0];
if(l == 1 && !isalpha(ch)) //非字母的单字节操作符
return GetUnary(EL, ch, rank);
//处理字母字符串
for(j = 0; fname[j] != 0; j++) {//是否为已有的数学函数
if(strcmp(fname[j], buf) == 0) {
EL.type = 51 + j;
EL.isp = 4; EL.icp = 5;
return true;
}
}
if(GetVariable(EL, buf, rank)) {
return true;
}
return false;
}
Top
5 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 22:52:18 得分 0
bool Calculator::Construe_Numeric(element &EL, int &i, int &rank) const
{
char buf[MaxLength_of_Expression];
GetOperand(i, buf);
EL.type = 0;
EL.value = atof (buf);
rank++;
if (rank > 1) {
Error(ERR_MISS_OPERATOR, __LINE__);
return false;
}
return true;
}
bool Calculator::Construe_Operator(element &EL, int &i, int &rank)
{
char buf[MaxLength_of_VariableName];
if(!GetOperator(i, buf)) // 取得整个操作符的名称
return false; //发生错误
if(!GetElement(EL, buf, rank)) // 取得相应的属性
return false ; //发生错误
if(EL.type < 40 && EL.type > 20) // 若是双目操作符,rank自减1
rank--;
if (rank < 0) {
Error(ERR_MISS_OPERAND, __LINE__);
return false;
}
return true;
}
void Calculator::Construe(Queue<element> &IN)
{ // 把输入的表达式整理为中缀表达式
element EL;
char ch;
int rank = 0; //表达式等级
int i = 0;
EL.icp = 0; EL.isp = 0; EL.value = 0;
IN.Clear();
while((ch = Expression[i]) != '\0') { //扫描表达式
if(IsOperandChar(i)) { //处理数字
if(!Construe_Numeric(EL, i, rank))
return;
IN.Insert(EL);
continue;
}
if(ch == '(') {
EL.type = 20; EL.icp = 6; EL.isp = -1;
i++;
IN.Insert(EL);
continue;
}
if(ch == ')') {
EL.type = 40; EL.icp = 0; EL.isp = 0;
i++;
IN.Insert(EL);
continue;
}
if(IsOperatorChar(i)) { //处理操作符
if (!Construe_Operator(EL, i, rank))
return;
IN.Insert(EL);
continue;
}
} // end of while()
if(rank != 1)
Error(ERR_MISS_OPERAND, __LINE__);
return;
}
void Calculator::Conversion(Queue<element> &IN)
{ //转换中缀表达式为后缀式
element EL;
int type;
Stack<element> STE; // Stack to elements
PO.Clear();
while(!IN.IsEmpty()) { //依次取出中缀表达式的元素EL
EL = IN.Delete();
type = EL.type;
if(type < 20) { // 若是操作数
PO.Insert(EL);
continue;
}
if(STE.IsEmpty()) { // 栈空时,操作符直接压栈
STE.Push(EL);
continue;
}
if(type == OPTR_RIGHT_PARENTHESIS) { // 若为右括号
while(!STE.IsEmpty() \
&& STE.Peek().type != OPTR_LEFT_PARENTHESIS) { // 取出左括号之前的操作符
EL = STE.Pop();
PO.Insert(EL);
}
if(STE.IsEmpty()) {
Error(ERR_MISS_LEFT_PARENTHESIS, __LINE__);
return;
}
STE.Pop(); // 弹出左括号
continue;
}
if(STE.Peek().isp < EL.icp) // 栈外优先级高,则直接把EL压栈
STE.Push(EL);
else { // 否则弹出栈内的优先级比EL.icp高的元素
while(!STE.IsEmpty() && STE.Peek().isp >= EL.icp) {
PO.Insert(STE.Pop());
}
STE.Push(EL);
}
}
while(!STE.IsEmpty()) { // 栈内剩余的操作符送入中缀表达式PO
EL = STE.Pop();
if(EL.type == OPTR_LEFT_PARENTHESIS) {
Error(ERR_MISS_RIGHT_PARAENTHESIS, __LINE__);
return;
}
PO.Insert(EL);
}
}
bool Calculator::Input(char *exp)
{
Queue<element> IN;
Clear();
if (strlen(exp) > MaxLength_of_Expression) {
Error(ERR_EXPRESSION_TOO_LONG, __LINE__);
return false;
}
Trim(exp); // 去除表达式的非法字符
Construe(IN); // 整理为中缀表达式
if(GetErrorID() != ERR_NO_ERROR)
return false;
Conversion(IN); // 转换为后缀表达式
return GetErrorID() == 0;
}
double Calculator::Calculate(element EL, double x, double y) const
{ // 双目运算符的具体运算
int type = EL.type;
if (type > 20 && type < 40) //处理双目运算
switch(type) { // '+' , '-' , '*' , '/' , '^'
case OPTR_ADD : return ( x + y );
case OPTR_SUBTRACT : return ( x - y );
case OPTR_MULTIPLY : return ( x * y );
case OPTR_DIVIDE :
if (y == 0.0)
Error(ERR_DEVIDE_BY_ZERO, __LINE__);
else
return ( x / y );
break;
case OPTR_POWER : return (pow( x, y));
default : Error(ERR_INVALID_OPERATOR, __LINE__); return 0.0;
}
else {
Error(ERR_INVALID_OPERATOR, __LINE__);
return 0.0;
}
return 0.0;
}
double Calculator::Calculate(element EL, double x) const
{// 单目运算符的具体运算
static double (*fun[])(double)={sin, cos, tan, sqrt,
log10, log, cot, fabs, floor, asin, acos, atan, sinh,
cosh, tanh, exp, sqrt}; //*fname[]对应的C函数名,其中cot为自己写的
int type = EL.type;
if (type > 40) { //处理单目运算
switch(type) {
case OPTR_MINUS: return -x;
case OPTR_POSITIVE: return x;
}
if(type>50) //函数运算
return ((*fun[type-51])(x));
else {
Error(ERR_INVALID_OPERATOR, __LINE__); return 0.0;
}
}
else {
Error(ERR_INVALID_OPERATOR, __LINE__); return 0.0;
}
return 0.0;
}
bool Calculator::Compute(void)
{ // 后缀表达式求值
int i, l, type;
double x, y, r;
element EL;
Stack<double> ST; //Stack to operands
Queue<element> postfix(PO); // 将PO复制到postfix
ST.Clear();
l = postfix.GetLength();
for (i = 0; i < l; i++) { //逆波兰表达式求值
EL = postfix.Delete();
type = EL.type;
if (type < 20) { // 操作数直接压栈
if (type == 0) // 压入数字
ST.Push(EL.value);
else // 压入变量
ST.Push(Vars[type-1]);
continue;
}
if (type > 40) { // 单目操作符
x = ST.Pop();
r = Calculate(EL, x);
ST.Push(r);
continue;
}
if (type > 20 && type < 40) { // 双目操作符
y = ST.Pop(); x = ST.Pop();
r = Calculate(EL, x, y);
ST.Push(r);
continue;
}
}
if(!ST.IsEmpty()) { // 取出最后结果
Result = ST.Pop();
if (ST.IsEmpty())
return true;
else {
Error(ERR_MISS_OPERATOR, __LINE__);
return false;
}
}
else
Error(ERR_UNKNOWN_ERROR, __LINE__);
return false;
}
void Calculator::Test(void)
{ // 测试计算器的功能
int i, nv;
int errid;
char buf[1000];
const char *name;
const char *pch;
double varsfrom[MaxNumber_of_Variable], var;
cout << "Input a expression: "<<endl;
//cin.getline(buf, sizeof(buf));
fgets(buf, sizeof(buf), stdin);
if(!Input(buf)) {
errid = GetErrorID();
pch = GetErrorMessage(errid);
cout << endl << "ERROR : " << pch << "\nNear Line "<< GetErrorLineNo() <<endl;
return ;
}
nv = GetNumberOfVariables();
if (nv > 0) {
cout << "\nThere seems to be " << nv <<
" Variable(s) in your expression, please input them :" << endl;
for(i = 0; i < nv; i++) {
name = GetVariableName(i);
cout << "No." << i + 1 << " " << name << " = ";
cin >> var;
varsfrom[i] = var;
}
Assign(varsfrom);
}
if(!Compute()) {
errid = GetErrorID();
cout << endl << "ERROR : " << GetErrorMessage(errid) << "\nNear Line "<< GetErrorLineNo() << endl;
return ;
}
cout << "Answer: " << GetResult() << endl;
}
Top
6 楼vsfan（窘）回复于 2003-08-01 23:39:58 得分 0
看看图论中的树的后序遍历便可
Top
7 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 23:58:56 得分 0
澄清一下，上面的代码不是偶写滴，偶当然也不姓陈啦~Top
8 楼pushser（捕食者）回复于 2003-08-02 00:05:16 得分 0
看晕了，太多了！Top
9 楼kxen（雄鹰）回复于 2003-08-02 15:44:03 得分 0
Thanks to fireseed(奶油狗)Top
10 楼bluei（蓝之我）回复于 2003-08-02 16:06:14 得分 0
本科学编译技术时做过这个程序，好像没这么老长。
收藏，有空读读。Top
11 楼Riemann（）回复于 2003-08-03 19:55:43 得分 5
用逆波兰表达式，http://expert.csdn.net/Expert/topic/2059/2059607.xml?temp=.6472742Top
12 楼Riemann（）回复于 2003-08-03 20:13:43 得分 0
http://www.ai361.com/default.htm有四则表达式求值的代码。Top
