表达式求值，无论是逆波兰表达式方法，还是递归下降法，都是采取将表达式进行解析，使得解析之后的结果易于计算，逆波兰表达式方法解析的结果是用栈存储的，而递归下降法解析的结果是用树存储的。先看看递归下降法解析的结果。
表达式树5+3*6
要计算这个解析后的表达式就比较容易了，就是左子树的结果加上右子树的结果。
要解析为这个树，所用到的算法模型如下：
表达式 = 项 + 表达式 或
表达式 = 项 - 表达式 或
表达式 = 项
项 = 因子 * 项 或
项 = 因子 / 项 或
项 = 因子
因子 = 数字 或
因子 = -因子 或
因子 = ( 表达式 )
这个算法有一个问题，就是它的语法是右结合的，也就是说1-2+3会被解析为1-(2+3)，要更改这一点，可以变为左结合的，但是这样会导致无穷递归的情况，要解决无穷递归比较麻烦，一个简单的解决方案是改变表达式和项的定义，改变之后的结果如下.
表达式 = 多个项相加减
项 = 多个因子相乘除
此时，可以根据以上的定义，抽象出树的结点，具体的代码如下。
#include <iostream>
#include <cmath>
#include <vector>
class Noncopyable{
protected:
Noncopyable(){};
~Noncopyable(){};
private:
Noncopyable(const Noncopyable&);
const Noncopyable& operator=(const Noncopyable& noncopyable);
};
class Node : private Noncopyable{
public:
Node(){}
virtual double calculate() const = 0;
virtual ~Node(){};
};
class NumberNode:public Node{
public:
NumberNode(int number):number_(number){}
double calculate() const{
return number_;
}
private:
const double number_;
};
class UnaryNode:public Node{
public:
UnaryNode(Node *child):child_(child){}
~UnaryNode(){
delete child_;
}
protected:
Node* const child_;
};
class UMinusNode:public UnaryNode{
public:
UMinusNode(Node *child):UnaryNode(child){}
double calculate() const{
return -child_->calculate();
}
};
class BinaryNode:public Node{
public:
BinaryNode(Node *left, Node *right):left_(left),right_(right){}
~BinaryNode(){
delete left_;
delete right_;
}
protected:
Node* const left_;
Node* const right_;
};
class MutipleNode : public Node{
public:
MutipleNode(Node *child){
addChild(child,true);
}
~MutipleNode(){
std::vector<Node *>::iterator it;
for(it = children_.begin();it != children_.end();it++){
delete *it;
}
}
void addChild(Node *child, bool positivity){
children_.push_back(child);
positivity_.push_back(positivity);
}
protected:
std::vector<Node *> children_;
std::vector<bool> positivity_;
};
class SumNode : public MutipleNode{
public:
SumNode(Node *node):MutipleNode(node){}
double calculate() const{
double res = 0.0;
for(int i=0;i<children_.size();i++){
if(positivity_[i] == true){
res += children_[i]->calculate();
}else{
res -= children_[i]->calculate();
}
}
return res;
}
};
class ProductNode : public MutipleNode{
public:
ProductNode(Node *node):MutipleNode(node){}
double calculate() const{
double res = 1.0;
for(int i=0;i<children_.size();i++){
if(positivity_[i] == true){
res *= children_[i]->calculate();
}else if(children_[i]->calculate() != 0.0){
res /= children_[i]->calculate();
}else{
res = HUGE_VAL;
}
}
return res;
}
};
可见，已知表达式树，要求解表达式是很容易的，只需要在根节点调用calculate方法即可。此外，还需要一个类来执行对字符的扫描。
#include <string>
#include <cctype>
class Scanner{
public:
enum Token{
TOKEN_END,
TOKEN_ERROR,
TOKEN_NUMBER,
TOKEN_PLUS,
TOKEN_MINUS,
TOKEN_MULTIPLY,
TOKEN_DIVIDE,
TOKEN_LPARENTHESIS,
TOKEN_RPARENTHESIS,
TOKEN_IDENTIFIER,
TOKEN_ASSIGN
};
Scanner(std::string& buf):buf_(buf),curPos_(0){
accept();
}
Token getToken() const{
return token_;
}
double getNumber() const{
return number_;
}
void accept(){
skipeWhite();
switch (buf_[curPos_]){
case '+':
token_ = TOKEN_PLUS;
curPos_++;
break;
case '-':
token_ = TOKEN_MINUS;
curPos_++;
break;
case '*':
token_ = TOKEN_MULTIPLY;
curPos_++;
break;
case '/':
token_ = TOKEN_DIVIDE;
curPos_++;
break;
case '(':
token_ = TOKEN_LPARENTHESIS;
curPos_++;
break;
case ')':
token_ = TOKEN_RPARENTHESIS;
curPos_++;
break;
case '0':case '1':case '2':case '3':case '4':
case '5':case '6':case '7':case '8':case '9':
case '.':
token_ = TOKEN_NUMBER;
char *p;
number_ = strtod(&buf_[curPos_],&p);
curPos_ = p - &buf_[0];
break;
case '\0':case '\r':case '\n':case EOF:
token_ = TOKEN_END;
break;
default:
token_ = TOKEN_ERROR;
break;
}
}
private:
void skipeWhite(){
while(isspace(buf_[curPos_])){
curPos_++;
}
}
Token token_;
double number_;
int curPos_;
const std::string& buf_;
};
关键是解析，其实这里解析写得比较简单，因为没有做异常处理，只需要根据定义一步一步写。值得注意的是，第一次看定义的时候，总感觉会无穷递归，但事实上，这种相互的调用是有出口的。这一点需要好好理解。下面是具体的代码。
#include "scanner.h"
#include "node.h"
class Parser{
public:
Parser(Scanner& scanner):scanner_(scanner){}
void parse(){
tree_ = expression();
}
double calculate() const{
return tree_->calculate();
}
private:
Node* expression(){
Node* node = term();
MutipleNode *ret = new SumNode(node);
Scanner::Token token = scanner_.getToken();
while(token == Scanner::TOKEN_PLUS || token == Scanner::TOKEN_MINUS){
scanner_.accept();
MutipleNode *node = term();
ret->addChild(node,token == Scanner::TOKEN_PLUS);
token = scanner_.getToken();
}
return ret;
}
MutipleNode* term(){
Node *node = factor();
MutipleNode *ret = new ProductNode(node);
Scanner::Token token = scanner_.getToken();
while(token == Scanner::TOKEN_MULTIPLY || token == Scanner::TOKEN_DIVIDE){
scanner_.accept();
node = factor();
ret->addChild(node,token + Scanner::TOKEN_MULTIPLY);
token = scanner_.getToken();
}
return ret;
}
Node* factor(){
Scanner::Token token = scanner_.getToken();
if(token == Scanner::TOKEN_NUMBER){ /* number */
scanner_.accept();
double number = scanner_.getNumber();
return new NumberNode(number);
}
else if(token == Scanner::TOKEN_MINUS){ /* -factor */
scanner_.accept();
Node *node = factor();
return new UMinusNode(node);
}
else if(token == Scanner::TOKEN_LPARENTHESIS){ /* ( expression ) */
scanner_.accept();
Node* node = expression();
if(scanner_.getToken() == Scanner::TOKEN_RPARENTHESIS){
scanner_.accept();
}else{
std::cout<<"Error: illegel branket."<<token<<std::endl;
}
return node;
}
return NULL;
}
Scanner& scanner_;
Node* tree_;
};
主函数如下：
int main(int argc, char const *argv[])
{
std::string s;
do{
std::cout<<"> ";
std::getline(std::cin,s);
Scanner scanner(s);
Parser parser(scanner);
parser.parse();
double ret = parser.calculate();
std::cout<< ret << std::endl;
}while(1);
return 0;
}
这里只是把最基本的东西展示出来了，需要优化的地方有很多，比如支持变量的定义，支持属性函数等。但个人感觉，这里已经把这个算法的核心展示出来了。
网友评论