Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Sample Input :
1
+ 30 - 10 15
1
* 5 + 2 - * 1 3 2
1
/ + 10 2 / 3 * 2 4
2
2 + 3 * 4
2
2 * ( 3 + 4 ) * 5
2
( 3 + 2 ) * 5
3
3 5 +
3
6 3 / 1 4 - * 3 + 8 -

Sample Output :
preorder : + 30 - 10 15
inorder  : 30 + ( 10 - 15 )
postorder: 30 10 15 - +
 = 25.00
preorder : * 5 + 2 - * 1 3 2
inorder  : 5 * ( 2 + ( ( 1 * 3 ) - 2 ) )
postorder: 5 2 1 3 * 2 - + *
 = 15.00
preorder : / + 10 2 / 3 * 2 4
inorder  : ( 10 + 2 ) / ( 3 / ( 2 * 4 ) )
postorder: 10 2 + 3 2 4 * / /
 = 32.00
preorder : + 2 * 3 4
inorder  : 2 + ( 3 * 4 )
postorder: 2 3 4 * +
 = 14.00
preorder : * * 2 + 3 4 5
inorder  : ( 2 * ( 3 + 4 ) ) * 5
postorder: 2 3 4 + * 5 *
 = 70.00
preorder : * + 3 2 5
inorder  : ( 3 + 2 ) * 5
postorder: 3 2 + 5 *
 = 25.00
preorder : + 3 5
inorder  : 3 + 5
postorder: 3 5 +
 = 8.00
preorder : - + * / 6 3 - 1 4 3 8
inorder  : ( ( ( 6 / 3 ) * ( 1 - 4 ) ) + 3 ) - 8
postorder: 6 3 / 1 4 - * 3 + 8 -
 = -11.00

---

#include <cstdio>
#include <sstream>
#include <iostream>
using namespace std;
typedef struct {
    int l, r;
    int flag, num;
} Node;
Node Nd[100];
int size;
stringstream sin;
void pre_build(int idx) {
    string tmp;
    sin >> tmp;
    if((tmp[0] > '9' || tmp[0] < '0') && tmp.length() == 1) {
        Nd[idx].num = tmp[0];
        Nd[idx].flag = 0;
        Nd[idx].l = ++size;
        pre_build(size);
        Nd[idx].r = ++size;
        pre_build(size);
    } else {
        stringstream nin;
        nin << tmp;
        nin >> Nd[idx].num;
        Nd[idx].flag = 1;
        Nd[idx].l = Nd[idx].r = 0;
    }
}
void post_build(int idx) {
    string tmp;
    sin >> tmp;
    if((tmp[0] > '9' || tmp[0] < '0') && tmp.length() == 1) {
        Nd[idx].num = tmp[0];
        Nd[idx].flag = 0;
        Nd[idx].r = ++size;
        post_build(size);
        Nd[idx].l = ++size;
        post_build(size);
    } else {
        stringstream nin;
        nin << tmp;
        nin >> Nd[idx].num;
        Nd[idx].flag = 1;
        Nd[idx].l = Nd[idx].r = 0;
    }
}
int priority(string c) {
    switch(c[0]) {
        case '(':return 1;
        case ')':return 2;
        case '+':return 3;
        case '-':return 3;
        case '*':return 4;
        case '/':return 4;
        case '%':return 4;
    }
}
void in_build(string in) {
    string stk[100], post[100], tmp;
    int sIdx = -1, pIdx = -1;
    stringstream bin;
    bin << in;
    while(bin >> tmp) {
        if(!((tmp[0] > '9' || tmp[0] < '0') && tmp.length() == 1))
            post[++pIdx] = tmp;
        else {
            stk[++sIdx] = tmp;
            if(tmp == ")") {
                sIdx--;
                while(sIdx >= 0 && stk[sIdx] != "(")
                    post[++pIdx] = stk[sIdx--];
                sIdx--;
            } else {
                while(sIdx >= 1 && priority(stk[sIdx-1]) >= priority(stk[sIdx])
                        && stk[sIdx] != "(") {
                    post[++pIdx] = stk[sIdx-1];
                    stk[sIdx-1] = stk[sIdx];
                    sIdx--;
                }
            }
        }
    }
    while(sIdx >= 0)    post[++pIdx] = stk[sIdx--];
    while(pIdx >= 0) {
        sin << post[pIdx] << ' ';
        pIdx--;
    }
    post_build(1);
}
double calu(int idx) {
    if(Nd[idx].flag)    return Nd[idx].num;
    switch(Nd[idx].num) {
        case '+':
            return calu(Nd[idx].l)+calu(Nd[idx].r);
        case '-':
            return calu(Nd[idx].l)-calu(Nd[idx].r);
        case '*':
            return calu(Nd[idx].l)*calu(Nd[idx].r);
        default:
            return calu(Nd[idx].l)/calu(Nd[idx].r);
    }
}
void preorder(int idx) {
    if(Nd[idx].flag) {
        printf("%d ", Nd[idx].num);
    } else {
        printf("%c ", Nd[idx].num);
        preorder(Nd[idx].l);
        preorder(Nd[idx].r);
    }
}
void inorder(int idx) {
    if(Nd[idx].flag) {
        printf("%d ", Nd[idx].num);
    } else {
        if(!Nd[Nd[idx].l].flag)
            printf("( ");
        inorder(Nd[idx].l);
        if(!Nd[Nd[idx].l].flag)
            printf(") ");
        printf("%c ", Nd[idx].num);
        if(!Nd[Nd[idx].r].flag)
            printf("( ");
        inorder(Nd[idx].r);
        if(!Nd[Nd[idx].r].flag)
            printf(") ");
    }
}
void postorder(int idx) {
    if(Nd[idx].flag) {
        printf("%d ", Nd[idx].num);
    } else {
        postorder(Nd[idx].l);
        postorder(Nd[idx].r);
        printf("%c ", Nd[idx].num);
    }
}
int main() {
    int ch;
    string line;
    freopen("out.txt", "w+t", stdout);
    while(scanf("%d", &ch) == 1) {
        cin.ignore(100, '\n');
        getline(cin, line);
        sin.clear();
        size = 1;
        if(ch == 1) {
            sin << line;
            pre_build(1);
        } else if(ch == 2)
            in_build(line);
        else {
            stringstream tmp;
            string stk[100];
            int idx = 0;
            tmp << line;
            while(tmp >> stk[idx])
                idx++;
            idx--;
            while(idx >= 0) {
                sin << stk[idx] << ' ';
                idx--;
            }
            post_build(1);
        }
        printf("preorder : ");
            preorder(1);
        puts("");
        printf("inorder  : ");
            inorder(1);
        puts("");
        printf("postorder: ");
            postorder(1);
        puts("");
        printf(" = %.2lf\n", calu(1));
    }
    return 0;
}