2020-2021:teams:no_morning_training:week1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:week1 [2020/05/09 22:55] shaco |
2020-2021:teams:no_morning_training:week1 [2020/06/05 15:27] (当前版本) shaco ↷ 链接因页面移动而自动修正 |
||
|---|---|---|---|
| 行 25: | 行 25: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| - | * [[2020-2021:teams:no_morning_training:尺取法|尺取法]] | + | * [[2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法|尺取法]] |
| - | * [[2020-2021:teams:no_morning_training:前缀和|前缀和]] | + | * [[2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和|前缀和]] |
| （由于我太菜了所以写一点基础的） | （由于我太菜了所以写一点基础的） | ||
| === 比赛 === | === 比赛 === | ||
| 行 36: | 行 36: | ||
| ==== 王瑞琦 ==== | ==== 王瑞琦 ==== | ||
| - | 给出一个以=结尾的包含+-*/%()的式子，按运算规则计算其值。 | + | 一个模板题，[[2020-2021:teams:no_morning_training:表达式的计算]] |
| - | + | ||
| - | 给出的式子是中缀表达式，将其转化为后缀表达式求解。 | + | |
| - | + | ||
| - | 转换方法： | + | |
| - | + | ||
| - | 用队列存储运算符，栈辅助处理。对每个字符，规则如下： | + | |
| - | + | ||
| - | 1）若为数字，直接入队（当然，多位数字要提前处理一下） | + | |
| - | + | ||
| - | 2）若为运算符： | + | |
| - | + | ||
| - | 1.栈为空直接入栈 | + | |
| - | + | ||
| - | 2.优先级大于栈顶元素入栈 | + | |
| - | + | ||
| - | 3.优先级小于等于栈顶元素，则栈顶元素出栈入队，直到优先级大于栈顶元素。 | + | |
| - | + | ||
| - | 3）若为（，直接入栈 | + | |
| - | + | ||
| - | 4）若为），栈顶元素出栈入队，直到（，两个括号不入队。 | + | |
| - | + | ||
| - | 计算方法： | + | |
| - | + | ||
| - | 对于一个后缀表达式，用栈辅助计算 | + | |
| - | + | ||
| - | 从左至右扫描，若为数字，直接入栈，若为运算符，则将栈顶两个元素计算，计算结果入栈。 | + | |
| - | + | ||
| - | 直到最后留下一个数字，即为结果。 | + | |
| - | + | ||
| - | #include <stdio.h> | + | |
| - | #include <string.h> | + | |
| - | #include <stdlib.h> | + | |
| - | char stack[500]; | + | |
| - | int queue[500]; | + | |
| - | void calcu(int r,int top) | + | |
| - | { | + | |
| - | switch (stack[top]){ | + | |
| - | case '+':queue[r-1]=queue[r]+queue[r-1];break; | + | |
| - | case '-':queue[r-1]=queue[r-1]-queue[r];break; | + | |
| - | case '*':queue[r-1]=queue[r]*queue[r-1];break; | + | |
| - | case '/':queue[r-1]=queue[r-1]/queue[r];break; | + | |
| - | case '%':queue[r-1]=queue[r-1]%queue[r];break; | + | |
| - | } | + | |
| - | } | + | |
| - | int main() | + | |
| - | { | + | |
| - | char s[500]; | + | |
| - | int pr[300]={0}; | + | |
| - | pr[(int)'+']=pr[(int)'-']=1; | + | |
| - | pr[(int)'*']=pr[(int)'/']=pr[(int)'%']=2; | + | |
| - | pr[(int)'(']=0; | + | |
| - | gets(s); | + | |
| - | int top=0,r=0,i=0; | + | |
| - | while (s[i]!='=') | + | |
| - | { | + | |
| - | if (s[i]>='0'&&s[i]<='9') | + | |
| - | { | + | |
| - | int x=(int)s[i]-48; | + | |
| - | i++; | + | |
| - | while (s[i]>='0'&&s[i]<='9') | + | |
| - | { | + | |
| - | x=x*10+(int)s[i]-48; | + | |
| - | i++; | + | |
| - | } | + | |
| - | queue[++r]=x; | + | |
| - | i--; | + | |
| - | } | + | |
| - | else if (s[i]!='('&&s[i]!=')'&&s[i]!=' '){ | + | |
| - | if (top==0) stack[++top]=s[i]; | + | |
| - | else { | + | |
| - | if (pr[(int)s[i]]>pr[(int)stack[top]]) stack[++top]=s[i]; | + | |
| - | else { | + | |
| - | while (top!=0&&pr[(int)s[i]]<=pr[(int)stack[top]]) calcu(r--,top--); | + | |
| - | stack[++top]=s[i]; | + | |
| - | } | + | |
| - | } | + | |
| - | } | + | |
| - | else if (s[i]=='(') stack[++top]=s[i]; | + | |
| - | else if (s[i]==')') { | + | |
| - | while (stack[top]!='(') calcu(r--,top--); | + | |
| - | top--; | + | |
| - | } | + | |
| - | i++; | + | |
| - | } | + | |
| - | for (int i=top;i>=1;i--) calcu(r--,top--); | + | |
| - | printf("%d",queue[1]); | + | |
| - | return 0; | + | |
| - | } | + | |
2020-2021/teams/no_morning_training/week1.1589036141.txt.gz · 最后更改: 2020/05/09 22:55 由 shaco
