37 条题解
-
2
fenghao LV 10 @ 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
Empire-003 LV 9 @ 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
#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
编译通过...
├ 测试数据 01：答案正确... (47ms, 480KB)
├ 测试数据 02：答案正确... (31ms, 484KB)
├ 测试数据 03：答案正确... (31ms, 480KB)
├ 测试数据 04：答案正确... (0ms, 480KB)
├ 测试数据 05：答案正确... (31ms, 480KB)---|---|---|---|---|---|---|---|-
Accepted / 100 / 143ms / 484KB
看下面有人说用树……
我想问问怎么按后序遍历的顺序构造树……
还是用栈
一个栈是运算对象，一个栈是运算符
根据读入的运算符的不同进行不同的运算
注意：加法不加括号
除法必须加括号 -
1
G_D_inferno LV 10 @ 2009-11-03 19:37:34
表述不清
ABC++
严格应该是A+(B+C)，答案为A+B+C重复三次：
不影响结果的括号都可去除
不影响结果的括号都可去除
不影响结果的括号都可去除 -
0
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 1000char 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
1055176872 LV 9 @ 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 = 40var
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
youandmetz LV 8 @ 2009-11-03 19:26:23
什么破题啊，AB+CD*/FG/* 怎么会输出 (A+B)/(C*D)*F/G
难道除的优先级比乘高吗，要么就是我根本就没搞懂，火死了！！
( 2007-11-11 20:14:15 )FancyMouse
不影响结果的括号都可去除
同感 害我交了三次才成功
-
0
用栈进行转制，过程中根据运算顺序考虑是否加括号。。。
要求细心。。。居然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
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
编译通过...
├ 测试数据 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
编译通过...
├ 测试数据 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
gnaggnoyil LV 10 @ 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
smallapple LV 3 @ 2007-11-11 20:14:15
什么破题啊，AB+CD*/FG/* 怎么会输出 (A+B)/(C*D)*F/G
难道除的优先级比乘高吗，要么就是我根本就没搞懂，火死了！！ -
0
FancyMouse LV 3 @ 2007-11-09 13:33:38
不影响结果的括号都可去除
fenghao
LV 10
@ 2009-10-23 10:31:28
