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

高山

每周一练 第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++语言编写
如果喜欢，别忘了评分 ：

最佳答案

月排行榜 / 总排行榜

zhangjinxuan

2022-11-27 20:36:44

何必呢？

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

复制代码

跳转到最佳答案楼层

zhangjinxuan

何必呢？

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

复制代码

高山

@zhangjinxuan @编程追风梦 @陈尚涵 @元豪 @xiaosi4081 @漫星闪 @hveagle

zhangjinxuan

其实我有答案，就交给别人回答吧^_^

zhiwen

回复看看答案

编程追风梦

回去睡觉啦，白天再看

zhangjinxuan

还忘了一个！数字确定不会爆 int，题目要说出来啊，意思是，数字的大小最大是多少，最小是多少？

zhangjinxuan

就是说我们输入一个 11111111111111111+2222222222222222222222222222222 之类的算式我们是不是就歇菜了？

xiaosi4081

这......
提供个思路吧：
将从左到右运算优先级小的加括号
可以考虑用树

Clamb

zhangjinxuan 发表于 2022-11-28 08:01
就是说我们输入一个 11111111111111111+2222222222222222222222222222222 之类的算式我们是不是就歇菜了？{ ...

或许得写一个大数的模拟运算？

Clamb

瞧瞧摸出我的逆波兰板子

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. 
    
29. 
    
30. int binaryPow(int a, int b){        // a^b%mod
    
31.         int ans = 1;
    
32.         while(b > 0){
    
33.                 if(b & 1){
    
34.                         ans = ans * a % mod;
    
35.                 }
    
36.                 a = a * a % mod;
    
37.                 b >>= 1;
    
38.         }
    
39.         return ans;
    
40. }
    
41. 
    
42. double Calculate(double a, double b, char f)  // 进行加减乘除运算
    
43. {
    
44.     if(f=='+') return b+a;
    
45.     if(f=='-') return b-a;
    
46.     if(f=='*') return b*a;
    
47.     if(f=='/') return b/a;
    
48.     if(f=='^') return binaryPow(b,a);
    
49.     return 0;
    
50. }
    
51. 
    
52. int jud(char a)  // 判断优先级
    
53. {
    
54.         if(a=='^') return 3;
    
55.     if(a=='*'||a=='/') return 2;
    
56.     if(a=='-'||a=='+') return 1;
    
57.     return 0;
    
58. }   
    
59. 
    
60. int jud1(char a)  // 判断运算符
    
61. {
    
62.     if(a=='+'||a=='-'||a=='*'||a=='/'||a=='^') return 1;
    
63.     return 0;
    
64. }
    
65. 
    
66. 
    
67. char s[500];
    
68. char r[500];  // 存储逆波兰式的结果
    
69. int k;
    
70. void ReversePolish()   // 转化成逆波兰式
    
71. {
    
72.     mem(r);
    
73.     k = 0;
    
74.     int l = strlen(s);
    
75.     stack<char>q; // 临时栈（存储运算符）
    
76.     for(int i = 0; i < l; i++){
    
77.         if(s[i]==' ') continue;  // 去掉空格干扰
    
78.         if(isdigit(s[i])){   // 如果是运算数
    
79.             r[k++] = s[i];
    
80.             while(isdigit(s[i+1])&&i+1<l){
    
81.                 r[k++] = s[i+1];
    
82.                 ++i;
    
83.             }
    
84.             r[k++] = ' ';   // 用空格隔开
    
85.         }
    
86.         if(s[i]=='('){   // 左括号 直接入临时栈
    
87.             q.push(s[i]);
    
88.         }
    
89.         if(s[i]==')'){   // 右括号 将左右括号之间运算符放进逆波兰式中
    
90.             while(q.top()!='('){
    
91.                 r[k++] = q.top();
    
92.                 r[k++] = ' ';
    
93.                 q.pop();
    
94.             }
    
95.             q.pop();
    
96.         }
    
97.         while(jud1(s[i])==1){  // 运算符
    
98.             if(q.empty()||q.top()=='('||jud(s[i])>jud(q.top())){  
    
99.                 // 栈为空，栈顶为左括号，当前运算符优先级大于栈顶运算符入栈
    
100.                 q.push(s[i]);
     
101.                 break;
     
102.             }else{
     
103.                 // 将栈顶运算符放进逆波兰式中
     
104.                 r[k++] = q.top();
     
105.                 r[k++] = ' ';
     
106.                 q.pop();
     
107.             }
     
108.         }
     
109.     }
     
110.     // 如果临时栈不为空，将剩余运算符放进逆波兰式中
     
111.     while(!q.empty()){
     
112.         r[k++] = q.top();
     
113.         r[k++] = ' ';
     
114.         q.pop();
     
115.     }
     
116.     cout << "Reverse Polish:";
     
117.     for(int i = 0; i < k; i++) cout << r[i]; // 输出逆波兰式
     
118.     CE;
     
119. }
     
120. 
     
121. double Result()   // 计算逆波兰式
     
122. {
     
123.     stack<double>re;  // 存储运算数
     
124.     for(int i = 0; i < k; i++){
     
125.         if(isdigit(r[i])){   // 运算数直接入栈
     
126.             double x = r[i++]-'0';
     
127.             while(r[i]!=' '){
     
128.                 x = x*10+r[i++]-'0';
     
129.             }
     
130.             re.push(x);
     
131.         }else if(jud1(r[i])==1){  // 运算符 从栈顶取两个数运算，再将结果入栈
     
132.             double x1 = re.top();
     
133.             re.pop();
     
134.             double x2 = re.top();
     
135.             re.pop();
     
136.             // cout << x1 << " " << x2 << " " << r[i] << endl;
     
137.             double x3 = Calculate(x1,x2,r[i]);
     
138.             // cout << x3 << endl;
     
139.             re.push(x3);
     
140.         }
     
141.     }
     
142.     cout << "Result:";
     
143.     return re.top();
     
144. }
     
145. 
     
146. int main()
     
147. {   
     
148.     scanf("%s", s); // 读入一个四则运算
     
149.     ReversePolish();  // 转化成逆波兰式
     
150.     double op =  Result();  // 计算结果
     
151.     printf("%.2lf\n", op);
     
152.     return 0;
     
153. }
     
154. 
     

复制代码

zhangjinxuan

Clamb 发表于 2022-11-28 14:17
或许得写一个大数的模拟运算？

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

lxping

还不会正则表达式，不然应该可以更简单匹配~~

1. old = input("请输入计算式：")
   
2. 
   
3. old = old.replace("*", ")&")
   
4. old = old.replace("/", ")%")
   
5. old = old.replace("&", "*")
   
6. old = old.replace("%", "/")
   
7. 
   
8. templist = old.split(")")
   
9. temp = ""
   
10. for i in templist[:-1]:
    
11.     if "+" in i or "-" in i:
    
12.         i = i + ")"
    
13.         temp += i
    
14.     else:      
    
15.         temp += i
    
16.    
    
17. new = temp.count(")")*"(" + temp + templist[-1]
    
18. 
    
19. print(new)

复制代码

高山

lxping 发表于 2022-11-29 19:27

运行不过

lxping

高山 发表于 2022-11-29 19:30
运行不过

python呀~~，只会这个

高山

lxping 发表于 2022-11-29 19:32
python呀~~，只会这个

那……没办法
我是说C或C++