四则混合运算表达式分析求值程序

//============================================================================= // 标记类别 // Copyright (C) OSHacker Jan 20th, 2008, Qingzhen No.1 Middle Scholl // // 本程序用于对一个四则运算表达式进行求值，本程序只支持一种括号，即 // 圆括号'('、'), 计算结果以小数形式给出。 // // 操作符为: // 加: + // 减: - // 乘: * // 除: / // // 注意：目前的程序支持的最多标记数为5000个，包括括号、数、以及操作符 // 在内，你可以根据自己的需要进行修改。数的位数不及超过20位。不支持科 // 学计数法。 // ----------------作者注 //============================================================================= #include "stdafx.h" #include "token.h" #include "parser.h" #include "factory.h" #include "Exception.h" //----------------------------------------------------------------------------- // 词法分析类的实现：从中字符串中分析出所有标记； //----------------------------------------------------------------------------- void GrammarParser::Solve(char*expression, TokenTable &table, EvalFactory &fac) { if (0 == expression) throw Exception("无效参数: 输入表达式不能为空!"); char numberBuffer[MaxNumberWidth+1]; // 数字缓冲区 int numIndex = 0; // 数字指针; int dotCount = 0; // 小数点个数; char* pchar = expression; // 搜索指针 while(*pchar != '\0') { if (isdigit(*pchar) || '.'==*pchar) // 首先检查是否是数字，若是则进栈 { if (numIndex > MaxNumberWidth) throw Exception("溢出: 输入表达式中的数字太大, 无法处理!"); if ( '.' == *pchar ) ++dotCount; if ( dotCount > 1 ) { throw Exception("无效表达式: 含有无效数据!"); } numberBuffer[numIndex++] = *pchar; } else // 若是操作符，数字栈出栈转换数据 { if (numIndex > 0) // 要把数字栈里边的数放面操作符前面 { numberBuffer[numIndex] = '\0'; Number *pnum = static_cast<Number*>(fac.CreateToken(Token::NUM)); pnum->value = atof(numberBuffer); table.AddToken(pnum); numIndex = dotCount = 0; // 清空数字索引及小数点位数; } // 判断是否是空白字符 bool isSpace = (isspace(*pchar) != 0); if (!isSpace) { if (Operator::IsOper(*pchar)) { Operator *pop = static_cast<Operator*> ( fac.CreateToken(Token::OPER) ); pop->value = static_cast<Operator::OperType>(*pchar); table.AddToken(pop); } else if ('('==*pchar || ')'==*pchar) { Parenthesis *ppar = static_cast<Parenthesis*> ( fac.CreateToken(Token::LRP) ); ppar->value = static_cast<Parenthesis::LRPType> (*pchar); table.AddToken(ppar); } else { throw Exception("无效表达式: 输入表达式中含有无效字符!"); } } } // 指针向后继续搜索 ++pchar; } // 最后检查数字栈里是否还有数，若有，则应转化入标记表 if (numIndex>0) { numberBuffer[numIndex] = '\0'; Number *pnum = static_cast<Number*>(fac.CreateToken(Token::NUM)); pnum->value = atof(numberBuffer); table.AddToken(pnum); } } //----------------------------------------------------------------------------- // 树栈类实现 //----------------------------------------------------------------------------- // 构造函数 TreeStack::TreeStack() { top = 0; for (int i=0; i<StackSize; ++i) { tree[i] = 0; } } // 入栈 void TreeStack::Push(const SYNTAX_TREE tr) { if (IsFull()) { throw Exception("溢出: 进栈失败!"); } tree[top++] = tr; } // 出栈 SYNTAX_TREE TreeStack::Pop() { if (IsEmpty()) { throw Exception("溢出: 出栈失败!栈为空"); } return tree[--top]; } // 获取栈顶元素 const SYNTAX_TREE TreeStack::GetTop() { if (IsEmpty()) { throw Exception("溢出: 栈顶元素为空"); } return tree[top - 1]; } // 判断栈是否为空 bool TreeStack::IsEmpty() { return (0 == top); } // 判断栈是否已满 bool TreeStack::IsFull() { return top == StackSize; } // 清空栈 void TreeStack::Empty() { top = 0; } //----------------------------------------------------------------------------- // 语法解析器的实现： //----------------------------------------------------------------------------- // 对一个语法树进行求值 double SyntaxParser::Eval(SYNTAX_TREE tr, int &step, FILE* pf) { double rslt = 0.0; if (0 == tr) return rslt; if (tr->token->GetType() == Token::NUM) { return (static_cast<Number*>(tr->token))->value; } double lsh = Eval(tr->lchild, step, pf); double rsh = Eval(tr->rchild, step, pf); Operator *pop = static_cast<Operator*>(tr->token); rslt = Operator::Calc(lsh, rsh, pop->value); // 写入计算过程 fprintf(pf, "%04d. %-20.6f %-10c %-20.6f =\t%-20.6f\n", step, lsh, static_cast<char>(pop->value), rsh, rslt); ++step; return rslt; } //---------------------------------------------------------------------------- // 对输入标记进行解析并求值 // 为简化解析过程，整个表达式可以看作是只有操作符和数值构成的标记表，括号内的表达式可以 // 在解析后进行求值，将所得的结果作为一个数值加点替换原来的括号表达式。因此，整过解析过程 // 中只需考虑操作符的优先级，遇到括号时，作为一棵子树的新解析开始。表达式中只有+,-,*,/ // 这个四个操作符。+和-以及*和/它们的优先级是分别相等的。*、/和优先级高于+、-。 //---------------------------------------------------------------------------- double SyntaxParser::Solve( TokenTable &table, // 标记表 TreeStack &stack, // 语法树栈 EvalFactory &fac, // 标记和树结点工厂 FILE *pf // 计算过程记录文件 ) { if (table.GetCount()==0) { throw Exception("输入表达式不能为空!"); } typedef Token::TokenType TokenType; SYNTAX_TREE tree = 0; // 语法树 int parSignal = 0; // 括号配对信号量，解析结束时若parSignal须为0 int step = 1; // 计算步骤 Token* prevTok = 0; // 前一标记 Token* firstTok = table[0]; // 第一个标记 Token* lastTok = table[table.GetCount()-1]; // 最后一个标记 // 首先检查首尾是否正确 if ((Token::OPER==firstTok->GetType() || Token::OPER==lastTok->GetType()) || ((Token::LRP==firstTok->GetType() && (static_cast<Parenthesis*>(firstTok))->value!=Parenthesis::LP)) || ((Token::LRP==lastTok->GetType() && (static_cast<Parenthesis*>(lastTok))->value!=Parenthesis::RP))) { throw Exception("无效表达式! 开头或结尾有误!"); } // 从标记表中提取每个标记，生成语法树 for (int i=0; i<table.GetCount(); ++i) { Token* token = table[i]; if (token->GetType()==Token::LRP) // 如果输入标记是括号 { Parenthesis* pp = static_cast<Parenthesis*>(token); if (Parenthesis::LP == pp->value) // 当前标记是一个左括号 { if (prevTok && prevTok->GetType() != Token::OPER && (Token::LRP==prevTok->GetType() &&(static_cast<Parenthesis*>(prevTok))->value!=Parenthesis::LP)) { throw Exception("无效表达式:'('之前只能为操作符或'('"); } ++parSignal; // 信号量递增 stack.Push(tree); tree = 0; } else // 当前标记是一个右括号 { if (prevTok && (prevTok->GetType()==Token::OPER || (prevTok->GetType()==Token::LRP && (static_cast<Parenthesis*>(prevTok))->value==Parenthesis::LP))) { throw Exception("无效表达式:')'之前只能为数或')'"); } if (parSignal == 0) { // 检查左右括号是否匹配 throw Exception("无效表达式:'('和')'不匹配!");