2015
04-10

# 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;