首页 > ACM题库 > HDU-杭电 > hdu 3773 Parenthesis待解决[解题报告]C++
2015
04-10

hdu 3773 Parenthesis待解决[解题报告]C++

Parenthesis

问题描述 :

To a computer, there is no difference between the expression (((x)+(y))(t)) and (x+y)t; but, to a human, the latter is easier to read. When writing automatically generated expressions that a human may have to read, it is useful to minimize the number of parentheses in an expression. We assume expressions consist of only two operations:
addition (+) and multiplication (juxtaposition), and these operations act on single lower-case letter variables only. Specifically, here is the grammar for an expression E:
E : P | P ‘+’ E
P : F | F P
F : V | ‘(‘ E ‘)’
V : ‘a’ | ‘b’ | .. | ‘z’
The addition (+, as in x+y) and multiplication (juxtaposition, as in xy) operators are associative: x+(y+z)=(x+y)+z=x+y+z and x(yz)=(xy)z=xyz. Commutativity and distributivity of these operations should not be assumed. Parentheses have the highest precedence, followed by multiplication and then addition.

输入:

The input consists of a number of cases. Each case is given by one line that satisfies the grammar above. Each expression is at most 1000 characters long.

输出:

The input consists of a number of cases. Each case is given by one line that satisfies the grammar above. Each expression is at most 1000 characters long.

样例输入:

x
(x+(y+z))
(x+(yz))
(x+y(x+t))
x+y+xt

样例输出:

x
x+y+z
x+yz
x+y(x+t)
x+y+xt


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;