表达式的逆波兰式转化模板

使用方法

输入合法的表达式，加减乘除，可以带括号，例如：
a+b*(c-d)-e/f

模板

#include<iostream>
#include<string.h>
#include<string>
#include<stack>
//#include<math.h>
using namespace std;
#define mem(x,num) memset(x,num,sizeof(x))
const int N = 1e3 + 5;
const int defaultSize = 100;
int lson[N], rson[N];
int nc = 0;

char op[N];
void Init() {
    mem(lson, 0);
    mem(rson, 0);
    mem(op, 0);
    nc = 0;
}
int build_Tree(char s[], int l, int r) { // Build the expression tree
    int tag1 = -1, tag2 = -1, p = 0;// tag1 stand for add&sub is_exist,tag2 for muti&devide
    int u;
    if (r - l == 1) {// this is only one point in this interval,build it
        u = ++nc;
        lson[u] = rson[u] = 0;
        op[u]=s[l];
        return u;// return self num to fa Node
    }
    for (int i(l); i < r; i++) {
        switch (s[i])// s[i]
        {
        case '(':p++; break;
        case ')':p--; break;
        case '+':case '-':if(!p)tag1 = i; break;// if operator in (),continue
        case '*':case '/':if(!p)tag2 = i; break;
        }
    }
    if (tag1 < 0)tag1 = tag2;// no + or - outside
    if (tag1 < 0)return build_Tree(s, l + 1, r - 1); // no * or / outside mean all operator and num in ()
    u = ++nc;
    lson[u] = build_Tree(s, l, tag1);
    rson[u] = build_Tree(s, tag1 + 1, r);
    op[u] = s[tag1];
    return u;
}
void Post(int rt) {// Postorder
    if (lson[rt] != 0)Post(lson[rt]);
    if (rson[rt] != 0)Post(rson[rt]);
    cout << op[rt] << ' ';
}
int main() {
    char s[defaultSize];
    while (cin>>s) {
        Init();
        int n=0;
        build_Tree(s, 0,strlen(s));
        Post(1);
        cout << endl;
    }
    return 0;
}