brackets演讲稿.pptVIP

* （括）（号） （表）（达） （式） 确认有几个合法表达式。 有如下规定： 1.（）是个合法表达式； 2.如果S是合法表达式，则（S）也是个合法表达式； 3.如果A和B都是合法表达式，则AB也是合法表达式； 4.其他的表达式都不是合法表达式。 另外，一个包含“（”和“）”的表达式，中间可能有多个合法表达式（只对满足规定的最长表达式进行计数，如“（（））”和“（）（）”都只算一个，不是两个）。 输入一个长度不超过1000的包含“（”和“）”的非空字符串 输出合法表达式的个数 4 ( ) ( ( ) ( ( ) ( ( ) 输出示例 输入示例 分析题意，可以得出一个关键的结论：只要一串最长的左右括号（ ）完全配对，就只算一个合法表达式。所以我们只需要找到不配对的括号，就能知道有几个合法表达式，举个例子：（）（）（））（）（）（（）（），这种情况下就有2个不配对的括号，一共三个合法表达式。 这里，我们又得讨论第一个不配对的括号是不是在第一个，并且，还得讨论最后一个不配对的括号是不是在最后一个，依据不同情况来确定合法表达式的个数，这样一来讨论的情况比较繁琐。 因此，我们可以引入一个向量vectorint a 来存放记录不配对的括号的下标。 我们可以，每当输入一个“（” 或 “）”的时候将一个表示下标的变量 i++，并将其存入向量a中，不过需要将左右括号配对时，即“（” 和 “）”相邻，把这两个字符的下标值从向量中删除。 一直循环下去之后，我们可以想象到，最后，向量中存放的都是不能配对的字符的下标值。 运用栈来进行这个比较过程，即判断“（” 和 “）”是否相邻，我们可以将括号一个一个的入栈，当遇到无法与之前配对的时候，继续输入，当可以配对时，将“（）”组合从栈中删除。 关于“空栈”这种情况的说明： 考虑到我们在输入的过程中可能出现栈为空的情况，如果需要判断，则又得另加一句 if 语句，会造成程序一定程度的复杂性，因此，我们可以在最初的时候就在栈中放入一个右括号“）”，这样就永远不会出现空栈的情况了。因此，我们就需要先在向量a中放入一个元素0来与之对应。 a.push_back(0); v.push()); while((s=getchar())!=\n) if(v.top()==)||s==() { v.push(s); a.push_back(i); i++; } else { v.pop(); a.pop_back(); i++; } 最后，我们需要根据向量a中的元素分布来判断合法表达式的个数。 我们可以先来看一个例子——假如向量a中最终的内容为1,6,13,18。显而易见，这四个数中间夹着3组所谓的合法表达式的下标值，可以确定为至少有3个合法表达式，接下来，我们仅仅需要进一步讨论一下18是不是我们输入括号的总数，如果我们总数恰好为18，则答案SUM=3，否则，说明“18”后面还有一组合法表达式的下标值，这时候SUM=4（=3+1）。 然而，关于如何判断上例中的1,6,13,18中间夹着的3个合法表达式，我们可以用下列语句实现： if(a[i+1]!=a[i]+1) sum++; 这部分程序如下： if(a.size()==1) sum=1; else { if(a[a.size()-1]i-1) sum++; for(i=0;ia.size()-1;i++) if(a[i+1]!=a[i]+1) sum++; } *