c++ - 具有过度约束类的噩梦表达式树

Question

我无意中让我的学生过度约束了一个用于解决以下问题的共享类。我意识到这可能是这个网站的居民可能喜欢的问题。

第一个团队/函数 getNodes 使用带符号整数和四个操作 +、-、* 和/获取表示前缀表达式的字符串，并使用类 Node 生成相应的空终止标记链表，其中通过“右”指针链接的标记。

第二个团队/函数 getTree 获取类似的字符串，将其传递给 getNodes，并将结果节点重新链接为表达式树。

第三个团队/函数 evaluate，获取相似的字符串，将其传递给 getTree，并对结果表达式树求值以形成答案。

紧随其后的是过度约束的 exptree.h。这个问题必须通过只写上面定义的三个函数来解决，没有额外的函数。

#ifndef EXPTREE_H_
#define EXPTREE_H_

using namespace std;

enum Ops{ADD, SUB, MUL, DIV, NUM};

class Node {
   private:
        int num;
        Ops op;
        Node *left, *right;

    public:
        friend Node *getNodes(string d);
        friend Node *getTree(string d);
        friend int evaluate (string);
    };

int evaluate(string d);
Node *getNodes(string d);
Node *getTree(string d);
#endif

唯一可以使用的库是这些

#include <iostream>
#include <vector>
#include <string>
#include "exptree.h" 

对于那些担心我的学生的人，我今天要指出的是，只需几个放置得当的函数就可以轻松解决这个问题。我知道表达式树可以编码有理数而不仅仅是整数。我今天也会指出这一点。

这是我根据他们的规范给他们的驱动程序。

#include <iostream>
#include <string>
#include "exptree.h"
using namespace std;
void test(string s, int target) {
    int result = evaluate(s);
    if (result == target)
        cout << s << " correctly evaluates to " << target << endl;
    else
        cout << s << "(" << result 
             << ") incorrectly evaluates to " << target << endl;
}
int main() {
    test("42", 42);
    test("* - / 4 2 1 42", 42);
    test("* - / -4 +2 -1 2", -2);
    test("* - / -4 +2 -1 2            ", -2);
    test("* 9 6", 54);
    return 0;
}

你能以尽可能优雅的方式编写这三个函数来解决这个噩梦般的问题吗？

Answer 1

getNodes 和 getTree 函数在这些约束条件下编写起来非常简单，所以我直接跳到有趣的部分。您自然会递归地评估表达式树，但这不是这里的选项，因为 eval 函数只接受一个字符串。当然，您可以将剩余的树重新串化为前缀表达式，并对其递归调用 eval，但那将是愚蠢的。

首先，我将表达式树转换为后缀表达式，使用显式堆栈作为穷人的递归。然后我使用标准操作数堆栈对其进行评估。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
#include "exptree.h" 

int evaluate(string d){
    Node* tree = getTree(d);
   //convert tree to postfix for simpler evaluation
    vector<Node*> node_stack;
    node_stack.push_back(tree);
    Node postfix_head;
    Node* postfix_tail = &postfix_head;
    while(node_stack.size() > 0){
        Node* place = node_stack.back();
        if(place->left == 0){
             if(place->right == 0){
                 postfix_tail->right = place;
                 node_stack.pop_back();
             } else {
                 node_stack.push_back(place->right);
                 place->right = 0;
             }
        } else {
            node_stack.push_back(place->left);
            place->left = 0;
        }
    }
   //evaluate postfix
    Node* place = postfix_head.right;
    vector<int> stack;
    while(place != 0){
        if(place->op != NUM){
            int operand_a, operand_b;
            operand_b = stack.back();
            stack.pop_back();
            operand_a = stack.back();
            stack.pop_back();
            switch(place->op){
                case ADD:
                    stack.push_back(operand_a + operand_b);
                    break;
                case SUB:
                    stack.push_back(operand_a - operand_b);
                    break;
                case MUL:
                    stack.push_back(operand_a * operand_b);
                    break;
                case DIV:
                    stack.push_back(operand_a / operand_b);
                    break;
            }
        } else {
            stack.push_back(place->num);
        }
        place = place->right;
    }
    return stack.back();
}