6137. Removing BracketsConstraints
Time Limit: 1 secs, Memory Limit: 256 MB
Description
Mirko was bored at his chemistry class, so he played Bomb Switcher on his cell phone. Unfortunately, he was spotted and was given a ridiculously heavy assignment for homework. For a given valid math expression with brackets, he must find all different expressions that can be obtained by removing valid pairs of brackets from the original expression. Two expressions are different if there is a character at which they differ.For example, given (2+(2*2)+2), one can get (2+2*2+2), 2+(2*2)+2, and 2+2*2+2. (2+2*2)+2 and 2+(2*2+2) can?t be reached, since we would have to remove pairs of brackets that are not valid. More than one pairs of brackets can surround the same part of the expression.
Input
The first and only line of input contains one valid mathematical expression composed of nonnegative integers, basic arithmetic operations denoted with characters ?+?, ?*?, ?-? and ?/?, and brackets ?(? and ?)?.Given expression won?t have more than 200 characters, and will have at least one, and no more than 10 pairs of brackets. Each expression is guaranteed to have at least one pair of brackets.
Output
Output all different expressions that can be obtained by removing valid pairs of brackets, sorted lexicographically.
Sample Input样例1：(0/(0))样例2：(2+(2*2)+2)样例3：(1+(2*(3+4)))Sample Output样例1：(0/0) 0/(0) 0/0样例2：(2+2*2+2) 2+(2*2)+2 2+2*2+2样例3：(1+(2*3+4)) (1+2*(3+4)) (1+2*3+4) 1+(2*(3+4)) 1+(2*3+4) 1+2*(3+4) 1+2*3+4Problem Source
COCI 2012.4 2012年每周一赛第十一场
DFS，枚举所有，注意有可能会有（（1 + 2））的情况；
#include <iostream>#include <string>#include <string.h>#include <algorithm>using namespace std;string c[1050];//答案string数组char ori_in[205];//原来读入的字符串，，用于比较char in[205];//不断在DFS中变换的字符串int b_pos[11];//左括号位置int to_b_pos[11];//与左括号位置对应的用括号位置int counter = 0;//总共不同的答案数int brackets = 0;//括号对数bool was_here(int pos) {//检查是否已经出现过for (int i = 0; i < pos; i++) {if (c[i] == c[pos]) {return true;}}return false;}void push_in() {//存入答案数组for (int i = 0; i < (int)strlen(in); i++) {if (in[i] != ' ') {c[counter].push_back(in[i]);}}if (!was_here(counter)) {counter++;} else {c[counter].clear();}}void DFS(int pos) {if (pos == brackets) {if (strcmp(ori_in, in))push_in();return;}DFS(pos + 1);//当前位置括号不变in[b_pos[pos]] = ' ';in[to_b_pos[pos]] = ' ';DFS(pos + 1);//当前位置括号去掉in[b_pos[pos]] = '(';in[to_b_pos[pos]] = ')';}bool is_new(int pos, int count) {//计算括号数目的时候用于判断（是否已经出现过for (int i = 0; i < count; i++) {if (b_pos[i] == pos) {return false;}}return true;}int main() {ios_base::sync_with_stdio(false);cin >> in;strcpy(ori_in, in);brackets = 0;for (int i = 0; i < (int)strlen(in); i++) {if (in[i] == '(') {brackets++;}}int k = 0;for (int i = 0; i < (int)strlen(in); i++) {if (in[i] == ')') {for (int j = i – 1; j >= 0; j–) {if (in[j] == '(' && is_new(j, k)) {b_pos[k] = j;to_b_pos[k++] = i;break;}}}}DFS(0);sort(c, c + counter);//排序得字典序for (int i = 0; i < counter; i++) {cout << c[i] << endl;}return 0;}
呼唤你前往另一个地方，过上另一种生活。
