(C++) 用于评估返回不正确值的简单算术表达式的解析树

Question

我试图编写一个函数，该函数接受一个简单的算术方程，将其转换为解析树，并 returns 评估值。由于某种原因，返回的值根本不正确。（并不是说它有帮助，但是 Python 中编码的相同功能可以正常工作）。我已经重新检查了多次，但我无法找到问题所在。我测试了 BinaryTree class 和 build_parse_tree() 函数，它们似乎按预期工作。我很确定这是 eval_parse_tree() 函数的问题。请让我知道此实现的问题所在。

是的，我知道这个实现只适用于个位数，但这应该不是问题。

#include <iostream>
#include <vector>
using namespace std;

class BinaryTree{
private:
    char root;
    BinaryTree * left = NULL;
    BinaryTree * right = NULL;
public:
    BinaryTree(char root_val){
        // constructor
        root = root_val;
    }
    void insert_right(char value){
        BinaryTree * new_node = new BinaryTree(value);
        if(right == NULL)
            right = new_node;
        else{
            new_node -> right = right;
            right = new_node;
        }
    }
    void insert_left(char value){
        BinaryTree * new_node = new BinaryTree(value);
        if(left == NULL)
            left = new_node;
        else{
            new_node -> left = left;
            left = new_node;
        }
    }
    BinaryTree * get_right(){
        return right;
    }
    BinaryTree * get_left(){
        return left;
    }
    char get_root(){
        return root;
    }
    void set_root(char value){
        root = value;
    }
};

bool is_operator(char token){
    string ops = "+-/*";
    for(unsigned long long int i = 0; i < ops.length(); i++)
        if(ops[i] == token)
            return true;
    return false;
}

BinaryTree * build_parse_tree(string expr){
    vector <BinaryTree *> stack;
    BinaryTree * tree = new BinaryTree(' ');
    stack.push_back(tree);
    for(long long unsigned int i = 0; i < expr.length(); i++){
        if(expr[i] == '('){
            tree -> insert_left(' ');
            stack.push_back(tree);
            tree = tree -> get_left();
        }
        else if(isdigit(expr[i])){
            tree -> set_root(expr[i]);
            tree = stack.back();
            stack.pop_back();
        }
        else if(is_operator(expr[i])){
            tree -> set_root(expr[i]);
            tree -> insert_right(' ');
            stack.push_back(tree);
            tree = tree -> get_right();
        }
        else{
            tree = stack.back();
            stack.pop_back();
        }
    }
    return tree;
}

int eval_parse_tree(BinaryTree * tree){
    //cout << "Root: " << tree -> get_root() << endl;
    char op;
    int left, right;
    BinaryTree * left_child = tree -> get_left();
    BinaryTree * right_child = tree -> get_right();
    if(left_child && right_child){
        op = tree -> get_root();
        left = eval_parse_tree(left_child);
        right = eval_parse_tree(right_child);
        switch(op){
            case '+': return (int)left + (int)right;
            case '-': return (int)left - (int)right;
            case '*': return (int)left * (int)right;
            case '/': return (int)left / (int)right;
        }
    }
    else
        return tree -> get_root();
}

int main(void){
    cout << eval_parse_tree(build_parse_tree("(5+(2*7))")) << endl; //returns 2803, instead of 19
}

Answer 1

问题是您在计算字符而不是整数。您可能知道每个字符都有一个 Ascii 代码，即该字符的数字表示，用于计算。 '5'、'2' 和 '7' 的 Ascii 码分别是 53、50 和 55。

因此'5' + '2' * '7'确实是2083，因为它实际上是53 + 50 * 55。

一个简单的解决方法是替换

return tree -> get_root();

在 eval_parse_tree 和

return tree -> get_root() - '0';

(C++) 用于评估返回不正确值的简单算术表达式的解析树

(C++) Parse tree for evaluating simple arithmetic expressions returning incorrect value

c++

tree

binary-tree

arithmetic-expressions

parse-tree