POJ 3983 解题报告-白红宇

POJ 3983 解题报告

阅读量：4204 次

发布时间：2019-05-26

本文共 3308 字，大约阅读时间需要 11 分钟。

这道题是很有意思的快算24的题目。样例本身是有问题的，首先，由于括号的存在，解是不唯一的，其次，样例中给除法左右也加了括号：(1/5)，这导致加括号的规则比较模糊。

尽管从disucss知道测试例子只有一个，但还是当做不知道地做了。题目其实不是很好写。一开始用的是string, 用dfs构建expression str，然后再evaluate(str) 看是不是24，找到就退出。但是由于左括号的存在，构建过程本身就很复杂，需要考虑多个左括号的情况，更难的地方在于evaluate一个string。

最终的解法是用树：首先构建所有可能的expression tree，然后一一evaluate，找到就退出。表达树是递归地构建的，左右节点既可以是一个operand，比如5，也可以是一个子树。实现中使用了c++ inheritance. Tree和Operand class都继承了Node class。 Node是一个interface (c++ 中的纯虚class)，有两个接口: double evaluate() 和 string expr()。

这样做的好处是逻辑很清晰，扩展性也很好：可以轻松地改成5个数或更多。

由于测试样例，这里的括号规则是能加就加，除了最外层。

Accepted

284K

0MS

3029B

/* ID: thestor1 LANG: C++ TASK: poj3983 */#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;char OPRS[] = {'+', '-', '*', '/'};class Node{public: virtual double evaluate() = 0; virtual string expr() = 0;};class Tree: public Node {public: char opr; Node *left, *right; Tree() {} Tree(char opr, Node *left, Node *right) { this->opr = opr; this->left = left; this->right = right; } double evaluate() { double lhs = left->evaluate(), rhs = right->evaluate(); switch (opr) { case '+' : return lhs + rhs; case '-' : return lhs - rhs; case '*' : return lhs * rhs; case '/' : return lhs / rhs; default : assert(false); return -1; } } string expr() { return "(" + left->expr() + opr + right->expr() + ")"; }};string toString(int num) { stringstream ss; ss << num; return ss.str();}class Operand: public Node{public: int opd; Operand() {} Operand(int opd) : opd(opd) {} double evaluate() { return opd; } string expr() { return toString(opd); }};bool toTree(Node* nodes[], int n, Node *&res) { // printf("[debug]nodes:\n"); // for (int i = 0; i < n; ++i) { // printf("%s\t", nodes[i]->expr().c_str()); // } // printf("\n"); // no need to merge nodes any more if (n == 1) { if (nodes[0]->evaluate() == 24) { res = nodes[0]; return true; } } Node** newNodes = new Node*[n - 1]; Tree* newNode = new Tree(); // iterate over pair of nodes to merge for (int i = 0; i < n - 1; ++i) { // copy nodes before nodes[i] for (int j = 0; j < i; ++j) { newNodes[j] = nodes[j]; } // merge nodes[i] and nodes[i + 1] // that is, newNode will be the parent newNode->left = nodes[i]; newNode->right = nodes[i + 1]; // newNodes[i] is now the merged node newNodes[i] = newNode; // copy nodes after nodes[i + 1] for (int j = i + 2; j < n; ++j) { newNodes[j - 1] = nodes[j]; } // iterate over every operator for (int j = 0; j < 4; ++ j) { newNode->opr = OPRS[j]; if (toTree(newNodes, n - 1, res)) { return true; } } } // can not find an expression tree that evalutes to 24 return false;}string to24(Operand* opds[]) { // 'res' points to the result expression tree Node *res = NULL; // construct a expression Tree that will evalute to 24 toTree((Node**)opds, 4, res); // assert that res is not NULL now // printf("[debug]res:%s\n", res->expr().c_str()); assert(res); // return the expression string from the expression tree string expr = res->expr(); // remove the outermost '()' return expr.substr(1, expr.size() - 2);}int main(){ int num; Operand* opds[4]; for (int i = 0; i < 4; ++i) { scanf("%d", &num); opds[i] = new Operand(num); } string expr = to24(opds); printf("%s\n", expr.c_str()); return 0;}

转载地址：http://gvxli.baihongyu.com/

你可能感兴趣的文章