C++高手请帮忙查错！ 300分。赢家独得！
背景： 网友Lawrence得到一个公式，想要展开。参http://www.csdn.net/expert/topic/964/964846.xml?temp=.5486872
我写了个hard-coded parser, 出了个问题，调了半天还不知道怎么回事。
如果我用一个简单一点的表达式， 运行正常；但用Lawrence兄的表达式[1900多字节]，会出现不能在try{}catch(...){}中俘获的异常：
可以通过的表达式：
char * formula =
// this formula has been truncated and runs without problem.
"((a[9] + (((((4 * ((((9 * (1 * n)) - a[7]) * n) - a[8])) +" //58
"((a[1] + (a[8] - a[4])) + ((a[9] - (6 * (8 * (11 * ((11 * n)"
"- a[9]))))) * n))) - (a[10] + (((9 * (((3 * ((3 * (6 * (a[10]"
"+ (4 * (a[8] - (3 * (a[1] + a[5]))))))) - a[8])) - (4 * ((((9 * n)"
"- a[7]) * n) - a[8]))) - (4 * ((((9 * n) - a[7]) * n) - a[8]))))"
"+ ((4 * ((a[8] - (11 * ((11 * n) - a[9]))) - a[8])) + a[7]))"
"- a[7]))) - ((((3 * n) - (7 * (6 * (a[10] + (6 * ((((a[8] - a[4])"
"- a[7]) * n) - a[8])))))) - a[1]) + (11 * ((11 * n) - a[9])))) -"
"(3 * (((a[9] - ((3 * (n - a[8])) + (((n * ((3 * (9 * (a[9] -"
"(a[9] + n)))) + ((11 * n) + (((a[9] + n) + (a[2] * ((11 * a[8])"
"+ (((((3 * a[4]) + (n * n)) - ((a[8] - a[4]) * (a[9] -"
"(a[9] + n)))) - ((((a[8] - a[4]) * (a[9] - (a[9] + n)))"
"- a[3]) - a[2])) - ((a[8] - a[4]) * (a[9] - (a[9] + n)))))))"
"- a[10])))) + (a[8] + ((11 * ((11 * n) - a[9])) + (9 * ((a[9]"
"+ (((a[9] - (6 * (a[10] + (((((a[4] + (a[4] + (a[1] + ((6 * a[3])"
"- (10 * (4 * ((11 * n) - a[8]))))))) - (7 * (n * n))) - a[1])"
"+ ((n * n) + a[7])) - a[7])))) * n) - ((8 * (11 * ((11 * n) -"
"a[9]))) + ((3 * ((3 * (6 * (a[10] + (4 * (a[8] - (3 * (a[1] +"
"a[5]))))))) - a[8])) - ((((((a[8] - a[4]) - a[7]) * n) - a[8])"
"- a[7]) * n))))) + (((a[8] + (((11 * n) - a[7]) + (8 * (11 *"
"((11 * n) - 8))))) * n) + (((a[8] + (((((a[8] - a[4]) - a[7])"
"* n) * n) + (8 * (((11 * n) - a[7]) * n)))) + (7 * (a[4] +"
"(a[1] + ((a[8] - a[4]) - (10 * (4 * (((11 * a[1]) * n) - a[8])"
"))))))) + ((((((11 * a[8]) + (4 * (((((11 * n) + ((a[8] - a[4])"
"- a[7])) - a[7]) * n) - a[8]))) - a[9]) + (a[8] - a[4])) +"
"(8 * (11 * ((7 * (a[8] - a[4])) - a[9])))))))))))))))))))))";
不能通过的表达式：
参：http://www.csdn.net/expert/topic/964/964846.xml?temp=.5486872
这是一个实际的问题，我和Lawrence都没有开玩笑。无论如何，找出这个问题的原因本身就是有意义的，欢迎大家实际测试。
我的环境： BCB6.0 SP1 + Win2K.
问题点数：200、回复次数：6Top
1 楼ALNG（?）回复于 2002-08-24 18:40:41 得分 0
//---------------------------------------------------------------------------
#pragma hdrstop
#include <list>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <ctype.h>
#include <stdlib.h>
#include <fstream>
std::ofstream of("output.txt");
// term 是因式链
struct term{
int coef; // coefficient;
std::list<std::string> factors;
term(int coef=1) : coef(coef){}
term(const char * s) : coef(1),factors(1,std::string(s)){}
term(const std::string& s) :coef(1),factors(1,s){}
term(const term& a) : coef(a.coef),factors(a.factors){}
term& operator *= (const term& rhs)
{
coef *= rhs.coef;
std::list<std::string> l( rhs.factors );
factors.merge(l);
return *this;
}
bool eq_rank(const term& rhs){
return factors == rhs.factors;
}
// write the content on s
void say_it(std::string& s){
{
std::stringstream sstr;
sstr << coef;
s += sstr.str();
}
if(factors.size()){
std::string hold,cur;
std::list<std::string>::iterator i=factors.begin();
hold = *i;
unsigned exp=1; // exponential;
for(++i ; i != factors.end(); ++i){
cur = *i;
if(cur == hold)
exp ++;
else{
s += "*" + hold;
hold = cur;
exp = 1;
if(exp>1){
std::stringstream sstr;
sstr << exp;
s += "^"+sstr.str();
}
}
}
s += "*" + hold;
if(exp>1){
std::stringstream sstr;
sstr << exp;
s += "^"+sstr.str();
}
}
}
// merge algorithm 使用
bool operator < (const term& rhs)const{
return factors < rhs.factors;
}
};
term operator * (const term& lhs, const term& rhs)
{
term tmp(lhs);
tmp *=rhs;
return tmp;
}
struct expression{
std::list<term> terms; // expression是term链
expression(){}
expression(const term& t) : terms(1,t){}
expression(const expression& e) :terms(e.terms){}
expression& operator +=(const expression& rhs)
{
std::list<term> l=rhs.terms;
terms.merge(l);
typedef std::list<term>::iterator iter;
unsigned cnt = terms.size(); // for debug;
for(iter i=terms.begin(); i !=terms.end(); ++i){
iter j= i;
for(++j; j != terms.end()&& j->eq_rank(*i);j=i,++j){
i->coef += j->coef;
terms.erase(j);
if(i->coef == 0){
#ifdef _DEBUG
of<<"removing 0 coeficient element\n";
of<<"pre:"<<say_it()<<std::endl;
of.flush();
#endif
i=terms.erase(i);
#ifdef _DEBUG
of<<"post:"<<say_it()<<std::endl;
of.flush();
#endif
}
}
}
return *this;
}
expression operator *=(const term& rhs){
for(std::list<term>::iterator i=terms.begin();
i != terms.end(); i++
)
*i *= rhs;
return *this;
}
expression& operator *= (const expression& rhs);
std::string say_it(){
std::string s;
say_it(s);
return s;
}
void say_it(std::string& s){
typedef std::list<term>::iterator iter;
if(terms.size()){
terms.front().say_it(s);
iter i = terms.begin();
for(++i; i != terms.end(); ++i){
bool b=i->coef<0;
s += b ? " - " : " + ";
if( b ) *i *= -1;
i->say_it(s);
if( b ) *i *= -1;
}
}
}
};
expression& expression::operator *= (const expression& rhs){
expression result;
for(std::list<term>::const_iterator i=rhs.terms.begin();
i != rhs.terms.end(); i++
){
expression tmp(*this);
tmp *= *i;
result += tmp;
}
this->terms.swap(result.terms);
return *this;
}
待续：Top
2 楼ALNG（?）回复于 2002-08-24 18:41:48 得分 0
class simplifier{
const char * expr; // 待化简表达式
int cur; // expr[cur] 当前位置
enum {EOI=0, ID=1, NUM =2};
private:
void advance(int off){
cur += off;
}
int peek(){ //peek next token
char c;
while( (c=expr[cur])!=0 && (c == ' ' || c == '\n' || c== 't'))
cur ++;
switch(c){
case EOI:
case '(':
case ')':
case '+':
case '-':
case '*':
case '[':
case ']':
return c;
default:
if( isdigit(c))
return NUM;
else if( isalpha(c) )
return ID;
else
throw std::runtime_error("unknown token");
}
}
// expr -> t
// | t + expr
// | t - expr
expression ex_expr(){
int t;
expression e(ex_term());
while((t=peek())=='+' || t == '-'){
advance(1);
expression tm = ex_term();
if(t == '-') tm *= -1;
e += tm;
}
return e;
}
// t -> f
// | f * t
expression ex_term(){
int t;
expression e(ex_factor());
while((t=peek())=='*'){
advance(1);
e *= ex_factor();
}
return e;
}
//
int get_num(){
int i = atoi(expr+cur);
while(isdigit(expr[++cur]))
;
return i;
}
std::string get_id(){
int tmp = cur;
while(isalnum(expr[++tmp]))
;
std::string s(expr+cur,expr+tmp);
cur = tmp;
if(peek()=='['){
std::string index;
advance(1);
int t = peek();
switch(t){
case NUM:{
int i = get_num();
std::stringstream ss;
ss<<i;
ss>>index;
break;
}
case ID:
index = get_id();
break;
default:
throw std::runtime_error("illegal ID format!");
}
if(peek()!=']')
throw std::runtime_error("illegal ID format!");
advance(1);
s += "[" + index + "]";
}
return s;
}
// f -> NUM | ID
// | ( expr )
expression ex_factor(){
int t=peek();
expression e;
switch(t){
case NUM:
return expression(term(get_num()));
case ID:
return expression(term(get_id()));
case '(':
advance(1);
e = ex_expr();
if(peek()!=')')
throw std::runtime_error("missing )");
advance(1);
break;
default:
throw std::runtime_error("fail to get a factor");
}
return e;
}
public:
simplifier(const char * expr):expr(expr),cur(0){}
expression simplify(){
expression e = ex_expr();
if(peek()!=EOI)
throw std::runtime_error("expression syntax");
return e;
}
};
extern char * formula;
#pragma argsused
int main(int argc, char* argv[])
{
using namespace std;
simplifier s(formula);
try{
expression e( s.simplify());
string s;
e.say_it(s);
cout<<s<<endl;
of<<s<<endl;
}catch(std::runtime_error& err){
cerr<<"runtime error:"<<err.what()<<endl;
}catch(...){
cerr<<"unknown error occurred!\n";
}
of.close();
return 0;
}
//---------------------------------------------------------------------------
char * formula =
// this formula has been truncated and runs without problem.
"((a[9] + (((((4 * ((((9 * (1 * n)) - a[7]) * n) - a[8])) +" //58
"((a[1] + (a[8] - a[4])) + ((a[9] - (6 * (8 * (11 * ((11 * n)"
"- a[9]))))) * n))) - (a[10] + (((9 * (((3 * ((3 * (6 * (a[10]"
"+ (4 * (a[8] - (3 * (a[1] + a[5]))))))) - a[8])) - (4 * ((((9 * n)"
"- a[7]) * n) - a[8]))) - (4 * ((((9 * n) - a[7]) * n) - a[8]))))"
"+ ((4 * ((a[8] - (11 * ((11 * n) - a[9]))) - a[8])) + a[7]))"
"- a[7]))) - ((((3 * n) - (7 * (6 * (a[10] + (6 * ((((a[8] - a[4])"
"- a[7]) * n) - a[8])))))) - a[1]) + (11 * ((11 * n) - a[9])))) -"
"(3 * (((a[9] - ((3 * (n - a[8])) + (((n * ((3 * (9 * (a[9] -"
"(a[9] + n)))) + ((11 * n) + (((a[9] + n) + (a[2] * ((11 * a[8])"
"+ (((((3 * a[4]) + (n * n)) - ((a[8] - a[4]) * (a[9] -"
"(a[9] + n)))) - ((((a[8] - a[4]) * (a[9] - (a[9] + n)))"
"- a[3]) - a[2])) - ((a[8] - a[4]) * (a[9] - (a[9] + n)))))))"
"- a[10])))) + (a[8] + ((11 * ((11 * n) - a[9])) + (9 * ((a[9]"
"+ (((a[9] - (6 * (a[10] + (((((a[4] + (a[4] + (a[1] + ((6 * a[3])"
"- (10 * (4 * ((11 * n) - a[8]))))))) - (7 * (n * n))) - a[1])"
"+ ((n * n) + a[7])) - a[7])))) * n) - ((8 * (11 * ((11 * n) -"
"a[9]))) + ((3 * ((3 * (6 * (a[10] + (4 * (a[8] - (3 * (a[1] +"
"a[5]))))))) - a[8])) - ((((((a[8] - a[4]) - a[7]) * n) - a[8])"
"- a[7]) * n))))) + (((a[8] + (((11 * n) - a[7]) + (8 * (11 *"
"((11 * n) - 8))))) * n) + (((a[8] + (((((a[8] - a[4]) - a[7])"
"* n) * n) + (8 * (((11 * n) - a[7]) * n)))) + (7 * (a[4] +"
"(a[1] + ((a[8] - a[4]) - (10 * (4 * (((11 * a[1]) * n) - a[8])"
"))))))) + ((((((11 * a[8]) + (4 * (((((11 * n) + ((a[8] - a[4])"
"- a[7])) - a[7]) * n) - a[8]))) - a[9]) + (a[8] - a[4])) +"
"(8 * (11 * ((7 * (a[8] - a[4])) - a[9])))))))))))))))))))))";
// this formula is the one provide by Lawrence
// unknown exception[s] occur somewhere when simplifier.cur
// is around 1596, and this exception cannot be caught with
// try{}catch(...){} pair.
/*
"((a[9] + (((((4 * ((((9 * (1 * n)) - a[7]) * n) - a[8])) +" //58
"((a[1] + (a[8] - a[4])) + ((a[9] - (6 * (8 * (11 * ((11 * n)"
"- a[9]))))) * n))) - (a[10] + (((9 * (((3 * ((3 * (6 * (a[10]"
"+ (4 * (a[8] - (3 * (a[1] + a[5]))))))) - a[8])) - (4 * ((((9 * n)"
"- a[7]) * n) - a[8]))) - (4 * ((((9 * n) - a[7]) * n) - a[8]))))"
"+ ((4 * ((a[8] - (11 * ((11 * n) - a[9]))) - a[8])) + a[7]))"
"- a[7]))) - ((((3 * n) - (7 * (6 * (a[10] + (6 * ((((a[8] - a[4])"
"- a[7]) * n) - a[8])))))) - a[1]) + (11 * ((11 * n) - a[9])))) -"
"(3 * (((a[9] - ((3 * (n - a[8])) + (((n * ((3 * (9 * (a[9] -"
"(a[9] + n)))) + ((11 * n) + (((a[9] + n) + (a[2] * ((11 * a[8])"
"+ (((((3 * a[4]) + (n * n)) - ((a[8] - a[4]) * (a[9] -"
"(a[9] + n)))) - ((((a[8] - a[4]) * (a[9] - (a[9] + n)))"
"- a[3]) - a[2])) - ((a[8] - a[4]) * (a[9] - (a[9] + n)))))))"
"- a[10])))) + (a[8] + ((11 * ((11 * n) - a[9])) + (9 * ((a[9]"
"+ (((a[9] - (6 * (a[10] + (((((a[4] + (a[4] + (a[1] + ((6 * a[3])"
"- (10 * (4 * ((11 * n) - a[8]))))))) - (7 * (n * n))) - a[1])"
"+ ((n * n) + a[7])) - a[7])))) * n) - ((8 * (11 * ((11 * n) -"
"a[9]))) + ((3 * ((3 * (6 * (a[10] + (4 * (a[8] - (3 * (a[1] +"
"a[5]))))))) - a[8])) - ((((((a[8] - a[4]) - a[7]) * n) - a[8])"
"- a[7]) * n))))) + (((a[8] + (((11 * n) - a[7]) + (8 * (11 *"
"((11 * n) - 8))))) * n) + (((a[8] + (((((a[8] - a[4]) - a[7])"
"* n) * n) + (8 * (((11 * n) - a[7]) * n)))) + (7 * (a[4] +"
"(a[1] + ((a[8] - a[4]) - (10 * (4 * (((11 * a[1]) * n) - a[8])"
"))))))) + ((((((11 * a[8]) + (4 * (((((11 * n) + ((a[8] - a[4])"
"- a[7])) - a[7]) * n) - a[8]))) - a[9]) + (a[8] - a[4])) +"
"(8 * (11 * ((7 * (a[8] - a[4])) - a[9])))) - (((((a[8] - a[4])"
"- a[7]) - a[8]) - (a[9] + n)) - (a[5] - (a[5] - (((a[2] * ((a[8]"
"- a[4]) + (11 * a[8]))) + (10 * (4 * ((((9 * (1 * n)) - a[7])"
"* n) - a[8])))) - a[8])))))))))))) + (a[8] - a[4])))) - a[9])"
"- a[9])))) + (((a[2] * (10 * (a[10] + (4 * (a[8] - (3 * (a[1]"
"+ a[5]))))))) - (10 * (4 * ((11 * a[1]) * n)))) + ((a[1] +"
"((a[8] - a[4]) - a[7])) + ((a[9] - (6 * (8 * (11 * ((11 * n)"
"- a[9]))))) * n))))";
*/
Top
3 楼kwok_1980（Mars）回复于 2002-08-24 19:10:25 得分 0
我太菜啦！
看不懂那一大串东东！Top
4 楼Lawrence444（胖子）回复于 2002-08-24 20:02:40 得分 200
ALNG, 我用VC运行你的程序，可以解析我的表达式，没有任何问题。
怀疑是你程序在C++ Builder里面栈空间溢出了（就好像我的遗传算法在表达式运算符个数达到400的时候出现的情况）。Top
5 楼ALNG（?）回复于 2002-08-24 20:26:00 得分 0
我也很怀疑是C++Builder用的STLPort的问题。
上次我用bitset居然不能编译，只好用回RW.
但是肯定不是栈溢出，估计是STLPort的源码在C++Builder的配置下有一点问题。
Top
6 楼ALNG（?）回复于 2002-08-24 21:18:14 得分 0
使用没有问题.
在文件开头加上:
#define _USE_OLD_RW_STL
就可以了.
被Borland打入冷宫的RW在可靠性上还是要好一些.
哪位能找出STLPort的毛病具体位置的不妨告诉我一下.Top
