题解

37 条题解

  • 2
    @ 2009-10-23 10:31:28

    轻松1次A。。

    注意以下几个事实:

    1、优先级大的在优先级小的前时后者加括号

    2、如果是-或/,同级运算后者加括号

    可能表达的不清楚,附上核心程序:

    if opt(ch)>stack[p-2].c then stack[p-2].s:='('+stack[p-2].s+')';

    if (opt(ch)>stack[p-1].c)or((opt(ch)=stack[p-1].c)and(ch in ['-','/'])) then

    stack[p-1].s:='('+stack[p-1].s+')';

    t:=stack[p-2].s+ch+stack[p-1].s;

    dec(p,2);

    stack[p].s:=t;

    stack[p].c:=opt(ch);

  • 1
    @ 2017-10-16 12:23:43
    /*
    主要的问题在于'-','/'符号的判定,方法有点简单粗暴
    如果是除法的第二个值,则检查是否有运算符,有的话加括号
    其他的话就检查加减运算符是否已经在括号中,'-'号同理
    有点混乱,如果有不对的地方恳请大神指点,谢谢_(_ _)_
    */
    #include <bits/stdc++.h>
     using namespace std;
    string charToString(char ch)
    {
        string tmp;
        stringstream ss;
        ss << ch;
        ss >> tmp;
        return tmp;
    }
    
    bool needBracket(char oper, string str, bool flag = true)//flag 为真则为第二个值,否则为第一个值
    {
        //return true;
        //cout << oper << " " << str << " " << flag << endl;
        int len = str.size();
        if(oper == '/' && flag)
        {
            for(int i = 0; i < len; i++)
                if(!(str[i] >= 'A' && str[i] <='Z'))
                    return true;
            
        }
        else
        {
            int tmp = 0;
            for(int i = 0; i < len; i++)
            {
                if(str[i] == '(') tmp++;
                else if(str[i] == ')') tmp--;
                else if((str[i] == '+' || str[i] == '-') && tmp <= 0) return true;
            }
        }
        return false;
    }
    
    int main()
    {
       
        stack<string> st;
        string firstValue, secondValue, tmp, str;
        cin >> str;
        int len = str.size();
        for(int i = 0; i < len; i++)
        {
            if(str[i] >= 'A' && str[i] <= 'Z')
                st.push(charToString(str[i]));
            else
                switch(str[i])
                {
                    case '+':
                        secondValue = st.top(); st.pop();
                        firstValue = st.top(); st.pop();
                        tmp = firstValue + "+" + secondValue;
                        st.push(tmp);
                        break;
                    case '-':
                        secondValue = st.top(); st.pop();
                        firstValue = st.top(); st.pop();
                        if(needBracket('-',secondValue, true))
                            tmp = firstValue + "-(" + secondValue + ")";
                        else
                            tmp = firstValue + "-" + secondValue;
                        st.push(tmp);
                        break;
                    case '*':
                        secondValue = st.top(); st.pop();
                        firstValue = st.top(); st.pop();
                        if(needBracket('*', secondValue, true))
                            secondValue = "(" + secondValue + ")";
                        tmp = firstValue + "*" + secondValue;
                        st.push(tmp);
                        break;
                    case '/':
                        secondValue = st.top(); st.pop();
                        firstValue = st.top(); st.pop();
                        if(needBracket('/', secondValue, true))
                            secondValue = "(" + secondValue + ")";
                        if(needBracket('/', firstValue, false))
                            firstValue = "(" + firstValue + ")";
                        tmp = firstValue + "/" + secondValue;
                        st.push(tmp);
                        break;
                }
        }
        cout << st.top() << endl;
        return 0;
    }
    
  • 1
    @ 2017-07-17 19:40:07

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    using namespace std;
    char a[1000][2];
    string s[1000];
    int zhan[1000];//存储每个左括号的位置
    int main()
    {
    //Part 1 输入以及初步转化
    int w=0;
    do
    {
    a[++w][0]=getchar();
    }while(a[w][0]!='\n');
    int top=0;
    for(int i=1;i<=w-1;i++)
    if(a[i][0]=='+'||a[i][0]=='-'||a[i][0]=='*'||a[i][0]=='/')
    {
    string r=s[top];
    string h=s[--top];
    if(i!=w-1) s[top]="("+h+a[i][0]+r+")";
    else s[top]=h+a[i][0]+r;
    }
    else
    s[++top]=a[i][0];
    //cout<<s[1]<<endl;

    //艰难地去括号
    int len=s[1].size();
    top=0;//指向括号栈zhan
    for(int i=0;i<=len-1;i++)
    {
    if(s[1][i]=='(') zhan[++top]=i;
    if(s[1][i]==')')//如果找到一个匹配的括号,那么,,可复杂了
    {
    int zuo=zhan[top--];//一个左括号出栈
    int you=i;

    //判断左括号的左边是什么

    int tmp=zuo-1;
    while(s[1][tmp]>='A'&&s[1][tmp]<='Z') tmp--;
    if(s[1][tmp]=='('||zuo==0)//左括号左边还是左括号,那么按照前面没有符号处理
    {
    int flag=1;//1表示要去括号,0表示不可去括号
    tmp=you+1;
    while(s[1][tmp]>='A'&&s[1][tmp]<='Z') tmp++;//找到右括号右边的第一个符号
    char r=s[1][tmp];//右边第一个符号一定不是右括号

    /*tmp=zuo+1;
    while(tmp<you)//找到括号内的符号
    {
    tmp++;
    if(s[1][tmp]=='+'||s[1][tmp]=='-')//只有括号外面是乘除,括号里面是加减,才不可去括号
    if(r=='*'||r=='/') flag=0;
    }*/
    int lstop=0;
    tmp=zuo+1;
    while(tmp<you)//找到括号内的不在其内的括号里的符号
    {
    if(s[1][tmp]=='(') lstop++;
    if(s[1][tmp]==')') lstop--;
    tmp++;
    if(lstop==0&&(s[1][tmp]=='+'||s[1][tmp]=='-'))
    if(r=='*'||r=='/') flag=0;
    }

    if(flag==1)
    {
    s[1][zuo]='#';
    s[1][you]='#';
    }
    }
    else//左括号左边是运算符,,那么可复杂了
    {
    int flag=1;//1表示要去括号,0表示不可去括号
    if(s[1][tmp]=='+')
    {
    tmp=you+1;
    while(s[1][tmp]<='A'&&s[1][tmp]>='Z') tmp++;//因为左边+括号内什么都可以去,所以看)右边的符号
    char r=s[1][tmp];//如果是右括号的话也不会改变flag的值

    /*tmp=zuo+1;
    while(tmp<you)//找括号内的符号
    {
    tmp++;
    if(s[1][tmp]=='+'||s[1][tmp]=='-')//只有括号外面是乘除,里面是加减才不可以去括号
    if(r=='*'||r=='/') flag=0;
    }*/
    int lstop=0;
    tmp=zuo+1;
    while(tmp<you)
    {
    if(s[1][tmp]=='(') lstop++;
    if(s[1][tmp]==')') lstop--;
    tmp++;
    if(lstop==0&&(s[1][tmp]=='+'||s[1][tmp]=='-'))
    if(r=='*'||r=='/') flag=0;
    }

    if(flag==1)
    {
    s[1][zuo]='#';
    s[1][you]='#';
    }
    }

    if(s[1][tmp]=='-'||s[1][tmp]=='*')//括号内是加减不可去,乘除可去(括号后面的符号对之无影响)
    {
    int flag=1;//1表示要去括号,0表示不可去括号
    /*tmp=zuo+1;
    while(tmp<you)//找括号内的符号
    {
    tmp++;
    if(s[1][tmp]=='+'||s[1][tmp]=='-') flag=0;
    }*/
    int lstop=0;
    tmp=zuo+1;
    while(tmp<you)
    {
    if(s[1][tmp]=='(') lstop++;
    if(s[1][tmp]==')') lstop--;
    tmp++;
    if(lstop==0&&(s[1][tmp]=='+'||s[1][tmp]=='-'))
    flag=0;
    }

    if(flag==1)
    {
    s[1][zuo]='#';
    s[1][you]='#';
    }
    }
    //当前一个符号为除号的时候,不管括号内是什么都不能去
    }
    }
    }
    for(int i=0;i<=len-1;i++)
    if(s[1][i]!='#') cout<<s[1][i];
    return 0;
    }

  • 1
    @ 2012-11-24 18:14:30

    编译通过...

    ├ 测试数据 01:答案正确... (47ms, 480KB)

    ├ 测试数据 02:答案正确... (31ms, 484KB)

    ├ 测试数据 03:答案正确... (31ms, 480KB)

    ├ 测试数据 04:答案正确... (0ms, 480KB)

    ├ 测试数据 05:答案正确... (31ms, 480KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 143ms / 484KB

    看下面有人说用树……

    我想问问怎么按后序遍历的顺序构造树……

    还是用栈

    一个栈是运算对象,一个栈是运算符

    根据读入的运算符的不同进行不同的运算

    注意:加法不加括号

    除法必须加括号

  • 1
    @ 2009-11-03 19:37:34

    表述不清

    ABC++

    严格应该是A+(B+C),答案为A+B+C

    重复三次:

    不影响结果的括号都可去除

    不影响结果的括号都可去除

    不影响结果的括号都可去除

  • 0
    @ 2015-11-26 18:07:33

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define N 1000

    char s[N] ="CAB+-";
    typedef struct _A{
    char op;
    char c;
    struct _A* l;
    struct _A* r;
    } Exp;
    void output(Exp* exp, char lop, char rop){
    if(exp->op==0) {putchar(exp->c);return;}
    int flag=0;
    if(exp->op=='+' || exp->op=='-'){
    if(lop != 0 && lop !='+') flag=1;
    else if(rop!=0 && rop!='+' && rop!='-') flag=1;
    }else{
    if(lop == '/') flag=1;
    }
    if(flag) putchar('(');
    output(exp->l,0,exp->op);
    putchar(exp->op);
    output(exp->r,exp->op,0);
    if(flag) putchar(')');
    }
    Exp* estack[N];
    int pointer;
    void push(Exp* exp){
    estack[pointer++] = exp;
    }
    Exp* pop(){
    return estack[--pointer];
    }
    char isEmpty(){
    return pointer == 0;
    }

    int main(){
    gets(s);
    char* ss=s;
    while(ss != '\0'){
    Exp
    e=(Exp*)malloc(sizeof(Exp));
    if(*ss == '+' || *ss == '-' || *ss == '/' || ss == ''){
    e->r = pop();
    e->l = pop();
    e->op = *ss;
    }else{
    e->op =0;
    e->c = *ss;
    }
    push(e);
    ss++;
    }
    output(pop(), 0,0);
    return 0;
    }

    呼,手机上打代码不容易。。。

  • 0
    @ 2013-11-03 11:27:51

    编译成功

    foo.pas(13,28) Warning: Variable "y" does not seem to be initialized
    测试数据 #0: Accepted, time = 0 ms, mem = 968 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 968 KiB, score = 20
    测试数据 #2: WrongAnswer, time = 0 ms, mem = 1076 KiB, score = 0
    测试数据 #3: WrongAnswer, time = 0 ms, mem = 928 KiB, score = 0
    测试数据 #4: WrongAnswer, time = 0 ms, mem = 932 KiB, score = 0
    WrongAnswer, time = 0 ms, mem = 1076 KiB, score = 40

    var
    s,u,v:ansistring;
    z:array[1..255]of ansistring;
    y:array[1..255]of char;
    i,l,top:longint;
    begin
    readln(s); l:=length(s); top:=0;
    for i:=1 to l do
    if s[i] in ['A'..'Z'] then
    begin inc(top); z[top]:=s[i]; end
    else begin
    dec(top); u:=z[top+1]; v:=z[top];
    if (s[i]='-')and(y[top+1]='+') then u:='('+u+')';
    if (s[i]='*')and(y[top+1] in ['+','-']) then u:='('+u+')';
    if (s[i]='/')and(y[top+1]<>' ') then u:='('+u+')';
    if (s[i] in ['*','/'])and(y[top] in ['+','-']) then v:='('+v+')';
    z[top]:=v+s[i]+u;
    if s[i] in ['+','-'] then y[top]:='+' else y[top]:='*';
    end;
    writeln(z[1]);
    end.

    呜呜 谁有数据。。。。。。。。。。。。。。。

  • 0
    @ 2009-11-03 19:26:23

    什么破题啊,AB+CD*/FG/* 怎么会输出 (A+B)/(C*D)*F/G

    难道除的优先级比乘高吗,要么就是我根本就没搞懂,火死了!!

    ( 2007-11-11 20:14:15 )

    FancyMouse

    不影响结果的括号都可去除

    同感 害我交了三次才成功

  • 0
    @ 2009-10-02 15:35:10

    用栈进行转制,过程中根据运算顺序考虑是否加括号。。。

    要求细心。。。居然3次才AC~~

    var s,u:string;

    stack:array[1..255]of string;

    c:array[1..255]of char;

    i,l,top:integer;

    begin

    readln(s);

    l:=length(s); top:=0;

    for i:=1 to l do

    if s[i] in ['A'..'Z'] then

    begin inc(top); stack[top]:=s[i]; c[top]:='a'; end

    else

    begin

    top:=top-1;

    u:=stack[top+1];

    if (s[i]='-')and(c[top+1]='+') then u:='('+u+')';

    if (s[i]='/')and(c[top+1]'a') then u:='('+u+')';

    if (s[i]='*')and(c[top+1]='+') then u:='('+u+')';

    if (c[top]='+')and(s[i] in ['*','/']) then stack[top]:='('+stack[top]+')';

    stack[top]:=stack[top]+s[i]+u;

    if s[i] in ['+','-'] then c[top]:='+' else c[top]:='*';

    end;

    writeln(stack[1]);

    end.

  • 0
    @ 2009-08-12 13:47:38

    const op : set of char = [[red]'+'[/red],[red]'-'[/red],[red]'*'[/red],[red]'/'[/red]];

    nu : set of char = [[red]'A'[/red]..[red]'Z'[/red]];

    var st : string;

    sn : array[[blue]1[/blue]..[blue]200[/blue]] of string;

    sp : array[[blue]1[/blue]..[blue]200[/blue]] of char;

    l,i,tn,tp : longint;

    function check(st:string):boolean;

    var l,i,ap : longint;

    flg : boolean;

    begin

    flg:=true;

    l:=length(st); i:=[blue]0[/blue]; ap:=0;

    repeat

    inc(i);

    if st[i] = [red]'('[/red] then flg:=false;

    if st[i] = [red]')'[/red] then flg:=true;

    if st[i] in op then

    if flg then

    if st[i] in [[red]'+'[/red],[red]'-'[/red]] then exit(false);

    until i = l ;

    exit(true);

    end;

    function doop(s[blue]1[/blue],s[blue]2[/blue]:string;top:char):string;

    var f[blue]1[/blue],f[blue]2[/blue] : boolean;

    begin

    f[blue]1[/blue]:=check(s[blue]1[/blue]);

    f[blue]2[/blue]:=check(s[blue]2[/blue]);

    if top = [red]'/'[/red] then

    if length(s[blue]2[/blue]) > [blue]1[/blue] then

    f[blue]2[/blue]:=false;

    if top in [[red]'-'[/red],[red]'*'[/red],[red]'/'[/red]] then

    begin

    if not f[blue]1[/blue] then s[blue]1[/blue]:=[red]'('[/red]+s[blue]1[/blue]+')';

    if not f[blue]2[/blue] then s[blue]2[/blue]:=[red]'('[/red]+s[blue]2[/blue]+')';

    end;

    exit(s[blue]1[/blue]+top+s[blue]2[/blue]);

    end;

    procedure cal;

    var top : char;

    flg,flg[blue]2[/blue] : boolean;

    i,j : longint;

    begin

    top:=sp[tp];

    sn[tn-[blue]1[/blue]]:=doop(sn[tn-[blue]1[/blue]],sn[tn],top);

    dec(tn); dec(tp);

    end;

    begin

    readln(st);

    l:=length(st);

    i:=[blue]0[/blue]; tn:=[blue]0[/blue]; tp:=0;

    repeat

    inc(i);

    if st[i] in nu then

    begin

    inc(tn);

    sn[tn]:=st[i];

    end;

    if st[i] in op then

    begin

    inc(tp);

    sp[tp]:=st[i];

    cal;

    end;

    until i = l;

    writeln(sn[[blue]1[/blue]]);

    end.

    if top = [red]'/'[/red] then

    if length(s[blue]2[/blue]) > [blue]1[/blue] then

    f[blue]2[/blue]:=false;

    一定要这个

  • 0
    @ 2009-07-22 21:34:33

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    注意除法后必须加括号

    #include

    #include

    using namespace std;

    string s1,s2,s3,fl,fs;

    string s[300];

    char f[300];

    int top,i;

    int main()

    {

    cin >> s1;

    top=0;

    for(i=0;i='A'&&s1[i]

  • 0
    @ 2009-06-13 13:01:55

    水题……先都+括号然后剔除OK了

  • 0
    @ 2008-10-27 20:32:26

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案错误...

     ├ Hint: 本Config.in为VijosConfig.ini制作工具生成,Copyright by CoVH Team ├ 标准行输出

     ├ 错误行输出

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:80 有效耗时:0ms

    啊啊啊啊啊啊啊啊啊啊

    5遍啊啊啊啊啊啊啊啊啊啊!!!

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2008-10-14 20:43:28

    我没带wjd的紫皮书,

    所以WA了一次才秒杀...

    program Project1;

    var s1,s2,s3:string;

    s:array[1..300]of string;

    sf:packed array[1..300]of char;

    top,i:integer;

    function pull:string;

    begin

    pull:=s[top];

    dec(top);

    end;

    procedure push(s1:string);

    begin

    inc(top);

    s[top]:=s1;

    end;

    begin

    readln(s1);

    s2:='';

    top:=0;

    for i:=1 to 300 do

    begin

    s[i]:='';

    end;

    i:=1;

    for i:=1 to length(s1) do

    case s1[i] of

    'A'..'Z':push(s1[i]);

    '+':begin

    s2:=pull;

    s3:=pull;

    push(s3+'+'+s2);

    sf[top]:='+';

    end;

    '-':begin

    s2:=pull;

    s3:=pull;

    if(sf[top+2]='+')or(sf[top+2]='-')

    then s2:='('+s2+')';

    push(s3+'-'+s2);

    sf[top]:='-';

    end;

    '*':begin

    s2:=pull;

    s3:=pull;

    if(sf[top+1]='+')or(sf[top+1]='-')

    then s3:='('+s3+')';

    if(sf[top+2]='+')or(sf[top+2]='-')

    then s2:='('+s2+')';

    push(s3+'*'+s2);

    sf[top]:='*';

    end;

    '/':begin

    s2:=pull;

    s3:=pull;

    if(sf[top+1]='+')or(sf[top+1]='-')

    then s3:='('+s3+')';

    if(sf[top+2]='+')or(sf[top+2]='-')or(sf[top+2]='*')or(sf[top+2]='/')

    then s2:='('+s2+')';

    push(s3+'/'+s2);

    sf[top]:='/';

    end;

    end;

    write(s[1]);

    end.

  • 0
    @ 2008-09-06 14:03:39

    这题挺有意思

  • 0
    @ 2008-08-07 14:18:38

    先用栈生成每一步运算都带有外括号的中缀表达式,再根据表达式内外运算符关系去掉冗余括号.一次ac,好高兴!

    !完成这题后,我上升到了2颗星!

  • 0
    @ 2008-07-15 14:50:50

    同级运算应该是从左到右啊!!!!!楼下的那个测试数据怎么是先除后乘了啊???数据超有问题!!!!!!!!!!!!1

  • 0
    @ 2007-11-11 20:14:15

    什么破题啊,AB+CD*/FG/* 怎么会输出 (A+B)/(C*D)*F/G

    难道除的优先级比乘高吗,要么就是我根本就没搞懂,火死了!!

  • 0
    @ 2007-11-09 13:33:38

    不影响结果的括号都可去除

  • 0
    @ 2007-11-08 22:01:50

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

信息

ID
1293
难度
6
分类
字符串 | 表达式处理 点击显示
标签
(无)
递交数
709
已通过
203
通过率
29%
被复制
2
上传者