鱼C论坛

 找回密码
 立即注册
查看: 1786|回复: 19

[已解决]【C\C++版块提升计划】每周一练第18期:适当加括号(限免)

[复制链接]
发表于 2022-11-27 20:36:43 | 显示全部楼层 |阅读模式
5鱼币
每周一练 第18期 适当加括号
作者
作者介绍
本帖作者:每周一练@tommyyu 自由投稿
原稿:https://fishc.com.cn/forum.php?m ... =221250&pid=6062618
声明内容
版权声明:转载于@dolly_yos2 (点此查看原稿
免责声明:本帖由“本帖作者”栏目的作者投稿,任何违规行为每周一练机构没有任何责任!!!
自由投稿:请前往 https://fishc.com.cn/thread-221250-1-1.html

                               
登录/注册后可看大图

题目
编写一个程序,在不改变算式的基础上,使这个程序对输入的算式的适当的地方加上括号,改变这个算式的运算顺序,以让这个算式能够从左往右逐步计算,且添加括号的数目尽可能少。只需要添加英文半角小括号这一种括号。
输入输出格式
输入:一个不带空格的算式,比如1*2*3*4,其中只有加、减、乘、除四种运算,分别用+、-、*、/四个符号来表示
输入输出样例
样例一:
输入
  1. 1+2+3*4
复制代码
输出
  1. (1+2+3)*4
复制代码
样例二:
输入
  1. 7+8*9+10
复制代码
输出
  1. (7+8)*9+10
复制代码
数据范围
输入的长度小于等于100 。

题解
游客,如果您要查看本帖隐藏内容请回复

代码:
游客,如果您要查看本帖隐藏内容请回复

[/hide]
奖励规则:
代码效率等方面最优,选为最佳答案,得到13鱼币+8荣誉+3贡献+1技术值
代码运行正确,奖励3鱼币
代码运行错误奖励将会折扣
仅支持使用C\C++语言编写
如果喜欢,别忘了评分



最佳答案
2022-11-27 20:36:44
本帖最后由 zhangjinxuan 于 2022-11-27 21:23 编辑

何必呢?
  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. char opts[101], c;
  4. int nums[101], n = 1;
  5. void solve(int l) {
  6.     bool flag = false;
  7.     if (l > 1) {
  8.         if ((opts[l] == '*' || opts[l] == '/') && (opts[l - 1] == '+' || opts[l - 1] == '-')) {
  9.             flag = true;
  10.             printf("(");
  11.         }
  12.         solve(l - 1);
  13.     } else printf("%d", nums[1]);
  14.     if (flag) printf(")");
  15.     printf("%c", opts[l]);
  16.     if (l != n) printf("%d", nums[l + 1]);
  17. }
  18. int main() {
  19.     scanf("%d", &nums[1]);
  20.     while ((c = getchar()) != '\n')  {
  21.         opts[n] = c;
  22.         scanf("%d", &nums[n + 1]);
  23.         ++n;
  24.     }
  25.     int st = clock();
  26.     solve(n);
  27.     int en = clock();
  28.     printf("\n用时:%dms", en - st);
  29.     return 0;
  30. }
复制代码

最佳答案

评分

参与人数 1鱼币 +5 收起 理由
zhangjinxuan + 5 无条件支持楼主!

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-27 20:36:44 | 显示全部楼层    本楼为最佳答案   
本帖最后由 zhangjinxuan 于 2022-11-27 21:23 编辑

何必呢?
  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. char opts[101], c;
  4. int nums[101], n = 1;
  5. void solve(int l) {
  6.     bool flag = false;
  7.     if (l > 1) {
  8.         if ((opts[l] == '*' || opts[l] == '/') && (opts[l - 1] == '+' || opts[l - 1] == '-')) {
  9.             flag = true;
  10.             printf("(");
  11.         }
  12.         solve(l - 1);
  13.     } else printf("%d", nums[1]);
  14.     if (flag) printf(")");
  15.     printf("%c", opts[l]);
  16.     if (l != n) printf("%d", nums[l + 1]);
  17. }
  18. int main() {
  19.     scanf("%d", &nums[1]);
  20.     while ((c = getchar()) != '\n')  {
  21.         opts[n] = c;
  22.         scanf("%d", &nums[n + 1]);
  23.         ++n;
  24.     }
  25.     int st = clock();
  26.     solve(n);
  27.     int en = clock();
  28.     printf("\n用时:%dms", en - st);
  29.     return 0;
  30. }
复制代码

点评

不错的啊  发表于 2022-11-28 18:22
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2022-11-27 20:36:44 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-27 21:01:15 | 显示全部楼层
其实我有答案,就交给别人回答吧^_^
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-27 21:07:46 | 显示全部楼层
回复看看答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-28 05:17:31 | 显示全部楼层
回去睡觉啦,白天再看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-28 08:00:39 | 显示全部楼层
还忘了一个!数字确定不会爆 int,题目要说出来啊,意思是,数字的大小最大是多少,最小是多少?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-28 08:01:34 | 显示全部楼层
就是说我们输入一个 11111111111111111+2222222222222222222222222222222 之类的算式我们是不是就歇菜了?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-28 14:17:33 | 显示全部楼层
这......
提供个思路吧:
将从左到右运算优先级小的加括号
可以考虑用树

点评

我也没办法 你问rommyyu  发表于 2022-11-28 20:22
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-28 14:17:41 | 显示全部楼层
zhangjinxuan 发表于 2022-11-28 08:01
就是说我们输入一个 11111111111111111+2222222222222222222222222222222 之类的算式我们是不是就歇菜了?{ ...

或许得写一个大数的模拟运算?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-28 14:20:56 | 显示全部楼层
瞧瞧摸出我的逆波兰板子
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pi acos(-1)
  4. #define mod 998244353
  5. #define INF 0x3f3f3f
  6. #define fi first
  7. #define se second
  8. #define it iterator
  9. #define ins insert
  10. #define mp make_pair
  11. #define pb push_back
  12. #define lb lower_bound
  13. #define ub upper_bound
  14. #define ll long long
  15. #define ull unsigned long long
  16. #define mem(a) memset(a,0,sizeof(a))
  17. #define cio ios::sync_with_stdio(false)
  18. #define gcd __gcd
  19. ll lgcd(ll a,ll b){return b == 0? a:lgcd(b, a % b);}
  20. int lowbit(int x){return x&(-x);}
  21. #define T int t;scanf("%d",&t);while(t--)
  22. #define CE cout << endl
  23. #define C(n) cout << n << endl
  24. #define CY cout << "YES" << endl
  25. #define CN cout << "NO" << endl
  26. #define Cy cout << "Yes" << endl
  27. #define Cn cout << "No" << endl


  28. int binaryPow(int a, int b){        // a^b%mod
  29.         int ans = 1;
  30.         while(b > 0){
  31.                 if(b & 1){
  32.                         ans = ans * a % mod;
  33.                 }
  34.                 a = a * a % mod;
  35.                 b >>= 1;
  36.         }
  37.         return ans;
  38. }

  39. double Calculate(double a, double b, char f)  // 进行加减乘除运算
  40. {
  41.     if(f=='+') return b+a;
  42.     if(f=='-') return b-a;
  43.     if(f=='*') return b*a;
  44.     if(f=='/') return b/a;
  45.     if(f=='^') return binaryPow(b,a);
  46.     return 0;
  47. }

  48. int jud(char a)  // 判断优先级
  49. {
  50.         if(a=='^') return 3;
  51.     if(a=='*'||a=='/') return 2;
  52.     if(a=='-'||a=='+') return 1;
  53.     return 0;
  54. }   

  55. int jud1(char a)  // 判断运算符
  56. {
  57.     if(a=='+'||a=='-'||a=='*'||a=='/'||a=='^') return 1;
  58.     return 0;
  59. }


  60. char s[500];
  61. char r[500];  // 存储逆波兰式的结果
  62. int k;
  63. void ReversePolish()   // 转化成逆波兰式
  64. {
  65.     mem(r);
  66.     k = 0;
  67.     int l = strlen(s);
  68.     stack<char>q; // 临时栈(存储运算符)
  69.     for(int i = 0; i < l; i++){
  70.         if(s[i]==' ') continue;  // 去掉空格干扰
  71.         if(isdigit(s[i])){   // 如果是运算数
  72.             r[k++] = s[i];
  73.             while(isdigit(s[i+1])&&i+1<l){
  74.                 r[k++] = s[i+1];
  75.                 ++i;
  76.             }
  77.             r[k++] = ' ';   // 用空格隔开
  78.         }
  79.         if(s[i]=='('){   // 左括号 直接入临时栈
  80.             q.push(s[i]);
  81.         }
  82.         if(s[i]==')'){   // 右括号 将左右括号之间运算符放进逆波兰式中
  83.             while(q.top()!='('){
  84.                 r[k++] = q.top();
  85.                 r[k++] = ' ';
  86.                 q.pop();
  87.             }
  88.             q.pop();
  89.         }
  90.         while(jud1(s[i])==1){  // 运算符
  91.             if(q.empty()||q.top()=='('||jud(s[i])>jud(q.top())){  
  92.                 // 栈为空,栈顶为左括号,当前运算符优先级大于栈顶运算符入栈
  93.                 q.push(s[i]);
  94.                 break;
  95.             }else{
  96.                 // 将栈顶运算符放进逆波兰式中
  97.                 r[k++] = q.top();
  98.                 r[k++] = ' ';
  99.                 q.pop();
  100.             }
  101.         }
  102.     }
  103.     // 如果临时栈不为空,将剩余运算符放进逆波兰式中
  104.     while(!q.empty()){
  105.         r[k++] = q.top();
  106.         r[k++] = ' ';
  107.         q.pop();
  108.     }
  109.     cout << "Reverse Polish:";
  110.     for(int i = 0; i < k; i++) cout << r[i]; // 输出逆波兰式
  111.     CE;
  112. }

  113. double Result()   // 计算逆波兰式
  114. {
  115.     stack<double>re;  // 存储运算数
  116.     for(int i = 0; i < k; i++){
  117.         if(isdigit(r[i])){   // 运算数直接入栈
  118.             double x = r[i++]-'0';
  119.             while(r[i]!=' '){
  120.                 x = x*10+r[i++]-'0';
  121.             }
  122.             re.push(x);
  123.         }else if(jud1(r[i])==1){  // 运算符 从栈顶取两个数运算,再将结果入栈
  124.             double x1 = re.top();
  125.             re.pop();
  126.             double x2 = re.top();
  127.             re.pop();
  128.             // cout << x1 << " " << x2 << " " << r[i] << endl;
  129.             double x3 = Calculate(x1,x2,r[i]);
  130.             // cout << x3 << endl;
  131.             re.push(x3);
  132.         }
  133.     }
  134.     cout << "Result:";
  135.     return re.top();
  136. }

  137. int main()
  138. {   
  139.     scanf("%s", s); // 读入一个四则运算
  140.     ReversePolish();  // 转化成逆波兰式
  141.     double op =  Result();  // 计算结果
  142.     printf("%.2lf\n", op);
  143.     return 0;
  144. }

复制代码

点评

代码效率不是很好。  发表于 2022-11-28 20:23

评分

参与人数 1贡献 +2 收起 理由
高山 + 2 感谢楼主无私奉献!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-28 14:25:25 | 显示全部楼层
Clamb 发表于 2022-11-28 14:17
或许得写一个大数的模拟运算?

没叫你运算,这样的话就只能运用大数读入,也麻烦不了多少

点评

我很赞同!: 5.0
我很赞同!: 5
可以!!!  发表于 2022-11-28 18:18
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-29 19:27:14 | 显示全部楼层
本帖最后由 lxping 于 2022-11-29 19:30 编辑

还不会正则表达式,不然应该可以更简单匹配~~
  1. old = input("请输入计算式:")

  2. old = old.replace("*", ")&")
  3. old = old.replace("/", ")%")
  4. old = old.replace("&", "*")
  5. old = old.replace("%", "/")

  6. templist = old.split(")")
  7. temp = ""
  8. for i in templist[:-1]:
  9.     if "+" in i or "-" in i:
  10.         i = i + ")"
  11.         temp += i
  12.     else:      
  13.         temp += i
  14.    
  15. new = temp.count(")")*"(" + temp + templist[-1]

  16. print(new)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2022-11-29 19:30:38 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-29 19:32:23 | 显示全部楼层

python呀~~,只会这个
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2022-11-29 19:38:32 | 显示全部楼层
lxping 发表于 2022-11-29 19:32
python呀~~,只会这个

那……没办法
我是说C或C++
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-19 19:29

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表