表达式求值问题

要求

我们给出一个表达式，将它转化为逆波兰式，传给树求值，例如1+2+3 转化为 12+3+

做法

匹配： 初始化一个栈stack，然后遍历这个逆波兰式的字符串，如果遇到数字，则以这个数字的值生成一个新的树节点，将这个节点入栈；如果遇到操作符，就以操作符为值生成一个新的树节点，弹栈弹出一个节点作为该新节点的右孩子节点，再弹出一个节点作为该新节点的左孩子节点，最后将该新节点入栈。遍历结束后，判断栈里的元素个数是否为1，如果为1则匹配成功；如果不为1则逆波兰式是非法的。
求值： 遍历树进行求值，具体做法看代码。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

#include <iostream>
#include <stack>
using namespace std;
struct treeNode{
    char val;
    treeNode* left;
    treeNode* right;
    treeNode(char val){
        this->val = val;
        this->left = nullptr;
        this->right = nullptr;
    }
};


class BSTree{
    treeNode* root;
public:
    BSTree(){
        root = nullptr;
    }
    /**
     *解析表达式字符串
     **/
    void parse(char str[]){
        const char* p = str;
        stack<treeNode*> stack;
        while (*p != '\0') {
            if (*p>='0' && *p<='9') {
                stack.push(new treeNode(*p));
            }else{
                treeNode* newNode = new treeNode(*p);
                treeNode* rightNode = stack.top();
                stack.pop();
                newNode->right = rightNode;
                treeNode* leftNode = stack.top();
                stack.pop();
                newNode->left = leftNode;
                stack.push(newNode);
            }
            p++;
        }
        if (stack.size()!=1) {
            cout<<"Illegal expression";
            root = nullptr;
        }else{
            root = stack.top();
        }


    }
    /**
     *计算表达式的值
     **/
    int evaluate(){
        if (root==nullptr) {
            cout<<" ";
            //如果表达式不规范返回int最小值
            return numeric_limits<int>::min();
        }else{
            return evaluate(root);
        }
    }
private:
    int evaluate(treeNode* node){
        switch (node->val) {
            case '+':
                return evaluate(node->left)+evaluate(node->right);

            case '-':
                return evaluate(node->left)-evaluate(node->right);

            case '*':
                return evaluate(node->left)*evaluate(node->right);

            case '/':
                return evaluate(node->left)/evaluate(node->right);
                ;
                //叶子节点
            default:
                return node->val - '0';
                ;
        }

    }
};

int main(int argc, const char * argv[]) {
    BSTree tree;
    tree.parse("44+22+/");
    cout<<tree.evaluate()<<endl;
    return 0;
}

Comments