文章

3

粉丝

354

获赞

2

访问

26.9k

头像
正向匹配+反向匹配
P1296 北京大学机试题
发布于2021年1月30日 14:23
阅读数 7.8k

括号匹配的思路就是左括号入栈,右括号的时候若栈里有元素就出栈匹配,最后若栈里还有左括号就匹配失败。按照这道题的话就是没有元素的时候就变成?,但是有一个问题就是栈里多余的左括号怎么变成$对应相应的位置呢????若是使用符号标记的话,例如"(()"与"()("这两种情况是不一样的,还是很难对应哪个左括号是多余的。

很简单的思路:1.首先直接输出s; 

                     2.接着就是顺序遍历s,建立一个顺序遍历的栈s1,按照符号匹配的方法,匹配不了的右括号变成?,最后不用管栈里有没有多余的左括号。

                     3.经过上轮操作,就是把多余的右括号变成普通字符了,之后就是要把多余左括号变成字符。

                     3.然后就是反向遍历s,建立一个反向遍历的栈s2,还是一样,只是右括号进栈,遇到左括号看看要不要出栈,匹配不了的左括号变成$,不用管栈里有没有多余的右括号了。

                     4.之后遍历一下就行了 不是?$的变成空格。

#include<bits/stdc++.h>
using namespace std;

int main(){

string s;
while(cin>>s){
	//先输出原先字符
    cout<<s<<endl;
    stack<char> stackzz,stackzz2;
    int leng = s.length();
    for(int i=0;i<leng;i++){
        //若是字...
登录查看完整内容


登录后发布评论

1 条评论
快乐小土狗
2024年4月2日 22:28

yes

赞(0)