题解 P1175 【表达式的转换】

wffms69_8 · 2016-09-18 11:19:18 · 题解

前几个题解都是用栈做的，我来个树做的

// CodeVS 2471
#include<cmath>
#include<stack>
#include<cctype>
#include<vector>
#include<string>
#include<iostream>
using namespace std;

struct Node {
    int lc, rc, num;
    char op;

    Node(int n, char o = '!', int l = -1, int r = -1)
        : op(o), lc(l), rc(r), num(n) {
    }
};

string expression;
vector<Node>tree;

int build(int left, int right) { // 左闭右开区间
    if (right - left == 1) { // 这是一个操作数
        tree.push_back(Node(expression[left] - '0')); // 新建树叶的节点
        return tree.size() - 1;
    }
    int parentheses(0), c1(-1), c2(-1), c3(-1); // c1,c2,c3记录优先级
    for (int i(left); i < right; ++i) // 找到这一区间括号外最右的+-，*/操作符的位置
        switch (expression[i]) {
        case '(':
            ++parentheses;
            break;
        case ')':
            --parentheses;
            break;
        case '+':
        case '-':
            if (!parentheses)
                c1 = i;
            break;
        case '*':
        case '/':
            if (!parentheses)
                c2 = i;
            break;
        case '^':
            if (!parentheses)
                c3 = i;
        }
    if (c1 < 0)
        c1 = c2; // 有加减，则加减是根节点，否则乘除是根节点
    if (c1 < 0)
        c1 = c3;
    if (c1 < 0) // 这是处理括号的情况；
            return build(left + 1, right - 1);
    // 根据找到的符号，建立左右子树
    tree.push_back(Node(0, expression[c1], build(left, c1),
        build(c1 + 1, right)));
    return tree.size() - 1;
}

void print(int node) {
    if (tree[node].lc < 0)
        cout << tree[node].num << ' ';
    else {
        print(tree[node].lc);
        print(tree[node].rc);
        cout << tree[node].op << ' ';
    }
}

void calculate(int node) {
    if (tree[node].lc < 0)
        return;
    calculate(tree[node].lc);
    calculate(tree[node].rc);
    int a(tree[tree[node].lc].num), b(tree[tree[node].rc].num);
    switch (tree[node].op) {
    case '+':
        a += b;
        break;
    case '-':
        a -= b;
        break;
    case '*':
        a *= b;
        break;
    case '/':
        a /= b;
        break;
    case '^':
        a = pow((double)a, b);
    }
    tree[node].num = a;
    tree[node].lc = tree[node].rc = -1;
    print(tree.size() - 1);
    cout << endl;
}

int main() {
    cin >> expression;
    build(0, expression.size());
    print(tree.size() - 1);
    cout << endl;
    calculate(tree.size() - 1);
    return 0;
}