JMK no matter what

SPOJ, CERC 2000

괄호와 사칙연산을 사용한 수식이 주어질 때, 수식의 시맨틱을 해치지 않는 범위 내에서 괄호를 최대한 제거하는 문제. 수식을 파싱해서 파스트리를 만들고 파스트리를 적절히 스트링으로 다시 바꾸면 된다. normalized form 만드는 것과 비슷한 듯. CERC 2007 문제 풀 때 썼던 간단 버전 파싱을 다시 짜 보았다.

예제에 있는 a-(b-c) 만 생각하고 a/(b/c) 예외 생각하지 않아서 1 WA. 바보다 -_-;

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;

char buf[512];
int precedence(char op)
{
    if(isalpha(op)) return 2;
    return op == '+' || op == '-' ? 0 : 1;
}

struct Node
{
    char op;
    Node *left, *right;
    Node(int l, int r)
    {
        while(true)
        {
            assert(l <= r);
            if(l == r)
            {
                op = buf[l];
                left = right = 0;
                return;
            }
            int br = 0;
            REP(pre,2)
                for(int i = r; i >= l; --i)
                    if(buf[i] == ')') ++br;
                    else if(buf[i] == '(') --br;
                    else if(br == 0 && !isalpha(buf[i]) && precedence(buf[i]) == pre)
                    {
                        left = new Node(l, i-1);
                        right = new Node(i+1, r);
                        op = buf[i];
                        return;
                    }
            ++l;
            --r;
        }
    }
    ~Node() { if(left) delete left; if(right) delete right; }
    string construct() const
    {
        if(isalpha(op)) return string(1, op);
        string le = left->construct();
        string re = right->construct();
        if(precedence(op) > precedence(left->op))
            le = "(" + le + ")";
        if(precedence(op) > precedence(right->op))
            re = "(" + re + ")";
        if(precedence(op) == precedence(right->op) && (op == '-' || op == '/'))
            re = "(" + re + ")";

        return le + op + re;
    }
};

int main()
{
    int cases;
    scanf("%d", &cases);
    for(int cc = 0; cc < cases; ++cc)
    {
        scanf("%s", buf);
        Node* root = new Node(0, strlen(buf)-1);
        cout << root->construct() << endl;
    }
}