KAI,

我很佩服你，或许又有人认为我蠢，连这都想不到。

但是还是认为想到树来解决问题是个最明智的选择。

这个问题在严蔚敏的数据结构上有明确的算法，只用到了栈。可能考虑起来没有树简单，但是从数据结构上比用树要简单的多了，另外优先级的问题不论用哪种数据结构都是不可避免的！

以上个人意见仅供参考！

[此贴子已经被作者于2006-7-26 17:54:45编辑过]

这个问题当然是到处都有了，我看过的一本书上用了3个小函数，就把一个可以带括号的表达市计算解决了，用的是间接递归函数。不过思想还是这个树的来的清楚

这家伙太强了吧...

以前写的，从书上半抄半改的，递归下降但没有用树，所以有过程，但状态没有保存。

[CODE]#include <iostream>
#include <string>
#include <cctype>
using namespace std;

enum token
{
NUMBER, LETTER, END,
PLUS='+', MINUS='-', MUL='*', DIV='/', //枚举值这样设置，比较的时候省事
PRINT=';', ASSIGN='=', LP='(', RP=')'
};

class calculator
{
private:
token currToken; //状态
string inputStr; //表达式缓存
int strIndex, NoOfError; //inputStr的索引，错误记数
double numValue; //存储 数值终结符

double expression(bool); //表达式
double term(bool); //项
double primary(bool); //因子

token getToken(); //词法分析

double getValue();
double error(const string&);

public:
calculator();
void getStatement();
int errNum() { return NoOfError; }
};

calculator::calculator()
{
currToken = PRINT;
strIndex = 0;
NoOfError = 0;
numValue = 0.0;
}

void calculator::getStatement()
{
getline(cin, inputStr); //输入表达式
inputStr += '\n';
cout<<inputStr<<endl;
while(1)
{
getToken();
if(currToken == END )
break;
else if(currToken == PRINT)
continue;
else
cout<<expression(false)<<endl; //启动分析
}
}

double calculator::expression(bool get)
{
double left = term(get);
while(true)
{
switch(currToken)
{
case PLUS : left += term(true);
break;
case MINUS :left -= term(true);
break;
default : return left;
}
}
}

double calculator::term(bool get)
{
double left = primary(get);
while(true)
{
switch(currToken)
{
case MUL : left *= primary(true);
break;
case DIV : if(double d = primary(true)) //判断d 是否为0
{
left /= d;
break;
}
return error(" is 0!");
default : return left;
}
}
}

double calculator::primary(bool get)
{
if(get) getToken();
double e;
switch(currToken)
{
case NUMBER :
e = numValue;
getToken();
return e;
case MINUS :
return -primary(true);
case LP :
e = expression(true);
if(currToken != RP)
return error(") expected");
getToken();
return e;
default : return error("primary expected");
}
}

token calculator::getToken()
{
char ch;
ch = inputStr[strIndex];
while(ch!='\n' && isspace(ch)) //越过空白符
ch = inputStr[++strIndex];
switch(ch)
{
case '\n' :
return currToken = END;
case '+': case '-': case '*': case '/':
case '(': case ')': case '=': case ';':
strIndex++;
return currToken = token(ch);
case '1': case '2': case '3': case '4': case '5':
case '6': case '7': case '8': case '9': case '0':
case '.':
numValue = getValue(); //取得终结符。
return currToken = NUMBER;
default:
error("bad token !");
strIndex++;
return currToken = PRINT;
}
}

double calculator::getValue() //string中的连续数字字符作为double提取出来.
{ //比较苯的办法
bool dot = false;
double e = 0;
double truth = 0.1;
char tmpStr[2];
tmpStr[1] = '\0';
while(strIndex < inputStr.size())
{
tmpStr[0] = inputStr[strIndex];
if( tmpStr[0] == '.')
dot = true;
else if(isdigit(tmpStr[0]))
{
if(!dot)
e = e*10 + atoi(tmpStr);
else
{
e = e + atoi(tmpStr)*truth;
truth *= truth;
}
}
else
return e;
strIndex++;
}
return e;
}

double calculator::error(const string &exstr)
{
cerr<<"error : "<<exstr<<endl;
NoOfError++;
return 1;
}

int main()
{
calculator cal;
cout<<"input:\n statement or statement1;statement2;..."<<endl;
cal.getStatement();
cout<<"error number : "<<cal.errNum()<<endl;
system("pause");
return 0;
}
[/CODE]


发现自己也有点看不懂了。

真是遇到高人了 我觉得发这个实在是有点惭愧了 自己还不知道自己的致命的错误 非常感谢KAI前辈 和各位回帖的高手 我会把数据结构好好学的 确实这个问题用树比用栈要好的多的多 还是自己内功实在不够啊 以后我会努力的
谢谢各位了 我还以为没人回了呢 呵呵

以下程序是前一断时间根据严蔚敏的《数据结构》基于栈的算法自己写的一个四则运算的小程序
其中的MyList是自己写的一个链表模板类，实现了简单的栈和队列操作。程序里面也有bug还没解决
比如说算式开始为负数在运算时就会出错，而且也没优化性能。这里贴出来一是希望高手们斧正，二就是抛砖引玉了。


#include "mylist.h" //所有的头文件都包含在里面了

//比较运算符优先级函数
int compareOper(char cOpBack, char cOpFront);
//判断是否运算符函数
int isOperator(char cOp);
//进行运算
double compute(double opnd1, double opnd2, char oper);
//括号匹配测试函数
bool matchBracket(MyList<char>& op);

void main()
{
MyList<char> stack_oper; //操作符栈
MyList<double> stack_opnd; //操作数栈
stack_oper.push('#');
string express; //表达式

getline(cin,express);
express+='#';
stringstream sIn(express); //输入流
char checkType; //用于测试输入流中的字符
double opNum;
MyList<char> tp;
for(;sIn>>checkType;)
if( isOperator(checkType) )//这段代码用来检测所输入的表达式是否合法特别是括号是否匹配
tp.push(checkType);
if(!matchBracket(tp))
{
cerr<<"Expression error!.";
exit(1);
}
sIn.clear();
sIn.seekg(ios::beg);
for(;sIn>>checkType;)
{
if( isOperator(checkType) )//操作符入栈并判断优先级进行计算
{
switch( compareOper( checkType, stack_oper.getTop() ) )
{
case 1:
if(checkType=='(')
stack_oper.push(')');
else
stack_oper.push(checkType);
break;

case 0:
stack_oper.pop();
break;

case -1:
{
double a=compute(stack_opnd.pop(),stack_opnd.pop(),stack_oper.pop());
stack_opnd.push(a);
sIn.seekg((int)sIn.tellg()-1);
break;
}

}
}
else
{
if( checkType>='0' && checkType<='9' )//操作数入栈
{
sIn.seekg( (int)sIn.tellg()-1);
sIn>>opNum;
stack_opnd.push(opNum);
}
else
{
cerr<<"Expression error! ";
exit(1);
}//if
}//if
}//for
if(!stack_oper.isEmpty())//表达式是否合法
{
cerr<<"Expression error!.";
exit(1);
}
else
cout<<"The result is "<<stack_opnd.getTop();
}//main

int compareOper(char cOpBack, char cOpFront)
{
if( cOpFront==')' && cOpBack == ')')
return 0;
if( cOpFront=='#' && cOpBack == '#')
return 0;
if( (isOperator(cOpFront)*10+1)-(isOperator(cOpBack)*10) > 0)
return -1;
if( (isOperator(cOpFront)*10+1)-(isOperator(cOpBack)*10) < 0)
return 1;
}//compareOper()

int isOperator(char cOp)
{
int PRI;
switch(cOp)
{
case '#':
PRI=-1;
break;

case '+':
case '-':
PRI=2;
break;

case '*':
case '/':
PRI=3;
break;

case '(':
PRI=4;
break;
case ')':
PRI=1;
break;

default:
PRI=0;
break;
}//switch
return PRI;
}//isOperator()

double compute(double opnd1, double opnd2, char oper)
{
switch(oper)
{
case '+':
return opnd1+opnd2;

case '-':
return opnd1-opnd2;

case '*':
return opnd1*opnd2;

case '/':
return opnd1/opnd2;
}//switch

}//compute()

bool matchBracket(MyList<char>& op)
{
MyList<char> temp;
for(int i=1; i<=op.itsLenth();i++)
{
char bracket=op[i];
if(bracket=='(')
temp.push(bracket);
if( bracket==')')
{
if(temp.isEmpty())
return 0;
else
temp.pop();
}
}

return temp.isEmpty();
}//matchBracket()

[此贴子已经被作者于2006-7-26 21:08:31编辑过]

actually, I want direct paste my code here, but I got an error info, that my program is larger than some size. So now I can only paste the file here.

when you got some bug, please tell me.

this program do work only when the expression is valid. I am writing the check function now.

this the new version with checking validity of the expression. please info me when you get some bug.