2022寒假集训day5

day5

五道栈的题加上字符串。

单调队列、

题目描述

假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。

输入格式

一行：表达式

输出格式

一行：“YES” 或“NO”

#include<bits/stdc++.h>

int a,sum=0;

char s[10005];

using namespace std;

int main(){

    cin>>s;

    for(int i=0;i<strlen(s);i++){

        if(s[i]==')') sum++;

        if(sum>a){

            cout<<"NO";

            return 0;

        }

        if(s[i]=='(') a++;

    }

    if(a!=sum)

        cout<<"NO";

    else

        cout<<"YES";

    return 0;

}

这题一开始写了八十分，第一个样例过了，就直接提交，80······

原来我的样例二没对。

最简单的题，刚开始就这样。

————————————————————————————————————————

括弧匹配检验

括弧匹配检验
描述
假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如 () 或 [([][])] 等为正确的匹配，[(]) 或( 或 (([)]) 均为错误的匹配。
现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？
输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出 “OK” ，不匹配就输出“Wrong”。输入一个字符串：[([][])]，输出：OK。

格式
输入格式
输入仅一行字符（字符个数小于255）。

输出格式
匹配就输出 “OK” ，不匹配就输出“Wrong”。

#include <bits/stdc++.h>

using namespace std;

char pipei(char ch)

{

    if(ch == ']')

        return '[';

    if(ch == ')')

        return '(';

    return 0;

}

void search(char *s)

{

    int i, top = 0;

    char ch;

    int n = strlen(s);

    int stk[n + 1];

    if(n%2==1)

    {

        cout<<"Wrong";

        return;

    }

    for(i=0;i<n;i++)

    {

        ch = pipei(s[i]);

        if(ch)

        {

            if(top==0||stk[top-1]!=ch)

            {

                cout<<"Wrong";

                return;

            }

            top--;

        }

        else

            stk[top++] = s[i];

    }

        if(top == 0)

            cout<<"OK";

        else

            cout<<"Wrong";

}

int main()

{

    int i;

    char s[256];

    cin>>s;;

    search(s);

}

题二首先搜索输入的括弧，并两两匹配

这块就取巧了：如果输入本来就是奇数，那么肯定不能匹配

if(n%2==1)

    {

        cout<<"Wrong";

        return;

    }

————————————————————————————————————————

字符串匹配问题

【题目描述】
字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输入: [()] 输出:YES，而输入([])，([)]都应该输出NO。

【输入】
第一行为一个整数n，表示以下有多少个由括好组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。

【输出】
在输出文件中有n行，每行都是YES或NO。

#include <bits/stdc++.h>

using namespace std;

char a[]={'{','[','(','<','}',']',')','>'},s[300];

int b[300],p[300];

int top;

int main(){

    int t,len,i,j,k,flag;

    cin>>t;

    while(t--){

        flag=1,top=0;

        cin>>s;

        len=strlen(s);

        for(i=0;i<len;i++)

            for(j=0;j<8;j++)

                if(s[i]==a[j]){

                    b[i]=j;

                    break;

                }

            i=0;//重复

        while(i<len){

            if(b[i]<=3)

                if(top==0||b[i]>=p[top]){

                    top++,p[top]=b[i];

                }else{

                    flag=0;

                    break;

                }

            else if(b[i]>=4){

                if(top>0&&p[top]+4==b[i]){

                    top--;

                }else{

                    flag=0;

                    break;

                }

            }

            i++;

        }

        if(top)printf("NO\n");

        else if(flag==1)printf("YES\n");

        else printf("NO\n");

    }

    return 0;

}

与之前的题不同的是，这个需要判断各种括号之间的包含关系是否合法。也是一个大坑

————————————————————————————————————————

计算

题目描述
小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，

门上有一个算式，其中只有 ( )，0 ~ 9 ，+ - * / ^，求出的值就是密码。

小明数学学得不好，还需你帮他的忙。(/ 用整数除法)

输入格式
共 1 行，为一个算式。

输出格式
共 1 行，就是密码。

输入样例
1+(3+2)(7^2+69)/(2)

输出样例
258

#include <bits/stdc++.h>

using namespace std;

stack<int> num;

stack<char> op;

map<char, int> Hash;

void panduan()

{

    int b=num.top(); num.pop();

    int a=num.top(); num.pop();

    char c=op.top(); op.pop();

    if(c=='+') num.push(a+b);

    if(c=='-') num.push(a-b);

    if(c=='*') num.push(a*b);

    if(c=='/') num.push(a/b);

    if(c=='^') num.push(pow(a,b));

}

int main()

{

    string s;

    cin>>s;

    Hash['+'] = Hash['-'] = 1;

    Hash['*'] = Hash['/'] = 2;

    Hash['^'] = 3;

    for (int i=0;i<s.size();i++)

    {

        if(s[i]>='0'&&s[i]<='9')

        {

            int j=i,n=0;

            while(j<s.size()&&isdigit(s[j])) n=n*10+(s[j++]-'0');

            num.push(n);

            i=j-1;

        }

        else if(s[i]=='(')

        {

            op.push(s[i]);

        }

        else if(s[i]==')')

        {

            while(op.top()!='(') panduan();

            op.pop();

        }

        else

        {

            while(op.size() && op.top()!='('&&Hash[op.top()]>=Hash[s[i]])

                panduan();

            if(s[i]=='-'&&(!i||s[i-1]=='('))

            {

                int j=i+1,n=0;

                while(j<s.size()&&isdigit(s[j])) n=n*10+(s[j++]-'0');

                num.push(-n);

                i=j-1;

            }

            else op.push(s[i]);

        }

    }

    while(op.size()) panduan();

    cout<<num.top()<<endl;

    return 0;

}

T4也是较为复杂的一题。

个人感觉与之前的计算器类似，此题就是加上括号和平方。

还要注意字符运算顺序。

————————————————————————————————————————

我愿称之为五颜六色。

巴特西

2022寒假集训day5

题目描述

输入格式

输出格式

最新文章

热门文章