总时间限制: 1000ms

内存限制: 65535kB

【描述】

众所周知，任何一个表达式，都可以用一棵表达式树来表示。例如，表达式a+b*c，可以表示为如下的表达式树：

   +
  / \
a   *
    / \
    b c

现在，给你一个中缀表达式，这个中缀表达式用变量来表示（不含数字），请你将这个中缀表达式用表达式二叉树的形式输出出来。

【输入】

输入分为三个部分。
第一部分为一行，即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量（a-z），也可能含有运算符（+、-、*、/、小括号），不含有数字，也不含有空格。
第二部分为一个整数n(n < 10)，表示中缀表达式的变量数。
第三部分有n行，每行格式为C　x，C为变量的字符，x为该变量的值。

【输出】

输出分为三个部分，第一个部分为该表达式的逆波兰式，即该表达式树的后根遍历结果。占一行。
第二部分为表达式树的显示，如样例输出所示。如果该二叉树是一棵满二叉树，则最底部的叶子结点，分别占据横坐标的第1、3、5、7……个位置（最左边的坐标是1），然后它们的父结点的横坐标，在两个子结点的中间。如果不是满二叉树，则没有结点的地方，用空格填充（但请略去所有的行末空格）。每一行父结点与子结点中隔开一行，用斜杠（/）与反斜杠（\）来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格，\出现的横坐标位置为父结点的横坐标偏右一格。也就是说，如果树高为m，则输出就有2m-1行。
第三部分为一个整数，表示将值代入变量之后，该中缀表达式的值。需要注意的一点是，除法代表整除运算，即舍弃小数点后的部分。同时，测试数据保证不会出现除以0的现象。

【样例输入】

a+b*c
3
a 2
b 7
c 5

【样例输出】

abc*+
   +
  / \
 a   *
    / \
    b c
37

【代码】 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <map>
#include <vector>
using namespace std;

map<char,int> priority = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'(', 0}};
map<char,int> value;

struct node_t {
    char val;
    node_t *left;
    node_t *right;
    node_t(char val_, node_t *left_ = NULL, node_t *right_ = NULL) : val(val_), left(left_), right(right_) {}
};

stack<char> op;
stack<node_t*> expression;
inline void doit()
{
    node_t *b = expression.top(); expression.pop();
    node_t *a = expression.top(); expression.pop();
    node_t *c = new node_t(op.top(), a, b); op.pop();
    expression.push(c);
}
node_t *build_tree(char *in) {
    int l = strlen(in);
    for (int i = 0; i < l; ++i) {
        if (isalpha(in[i])) {
            expression.push(new node_t(in[i]));
        }
        else {
            if (in[i] == '(')
                op.push(in[i]);
            else if (in[i] == ')') {
                while (op.top() != '(')
                    doit();
                op.pop(); // for '('
            }
            else {
                while (!op.empty() && priority[op.top()] >= priority[in[i]])
                    doit();
                op.push(in[i]);
            }
        }
    }
    while (!op.empty()) {
        doit();
    }
    return expression.top();
}

void postfix_dfs(node_t *cur){
    if (cur->left)
        postfix_dfs(cur->left);
    if (cur->right)
        postfix_dfs(cur->right);
    putchar(cur->val);
}

int cal(int a, int b, char o)
{
    if (o == '+') return a+b;
    if (o == '-') return a-b;
    if (o == '*') return a*b;
    if (o == '/') return a/b;
    cerr << "bad o" << endl;
    return 0;
}

int cal_tree(node_t* cur){
    if (isalpha(cur->val))
        return value[cur->val];
    return cal(cal_tree(cur->left), cal_tree(cur->right), cur->val);
}

int tree_height(node_t *cur)
{
    if (isalpha(cur->val))
        return 1;
    return 1+max(tree_height(cur->left), tree_height(cur->right));
}

void print_tree(node_t *rt)
{
    struct Node{
        node_t *node;
        int pos;
    };

    int tree_h = tree_height(rt);

    vector<Node> *v1 = new vector<Node>(), *v2 = new vector<Node>();
    v1->push_back({rt, (1<<(tree_h-1))-1});
    for (int h = tree_h; h >= 1; --h) {
        int last_pos = 0;
        int bias = 1<<(h-2);

        /* print node value */
        for (Node nd : *v1) {
            for (int i = last_pos; i < nd.pos; ++i)
                putchar(' ');
            putchar(nd.node->val);
            last_pos = nd.pos+1;
            if (h > 1 && !isalpha(nd.node->val)) {
                v2->push_back({nd.node->left, nd.pos - bias});
                v2->push_back({nd.node->right, nd.pos + bias});
            }
        }
        putchar('\n');

        if (h == 1)
            break;

        /* print branch */
        last_pos = 0;
        for (Node nd : *v1) {
            if (isalpha(nd.node->val))
                continue;
            for (int i = last_pos; i < nd.pos-1; ++i)
                putchar(' ');
            printf("/ \\");
            last_pos = nd.pos + 2;
        }
        putchar('\n');

        /* get ready for next loop */
        v1->clear();
        swap(v1, v2);
    }

}

int main()
{
    char in[55];
    cin >> in;

    node_t *rt = build_tree(in);

    postfix_dfs(rt);
    printf("\n");

    print_tree(rt);

    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        char c; int v;
        cin >> c >> v;
        value[c] = v;
    }
    cout << cal_tree(rt) << endl;

    system("pause");
    return 0;
}

【分析】

1. 借用“直接求中缀表达式”的思想，也可以有中缀表达式直接构建表达式树
2. 不同的地方在于，直接求中缀表达式时，我们把栈顶两个数的运算结果放回栈中，这次我们把栈顶两个节点拼成的新节点放回栈中
3. 由于数据规模太大，数组开不下，不能用dfs递归打印；改为使用bfs打印
4. 用last_pos标记的方法打印中间的空格是个好方法
5. 层次bfs的方法：队列不用queue结构而用vector结构，节点信息中不用存储深度信息；用两个vector指针，一轮循环结束时swap是方便的写法