【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
static/image/hrline/1.gif
题目
编写一个程序，在不改变算式的基础上，使这个程序对输入的算式的适当的地方加上括号，改变这个算式的运算顺序，以让这个算式能够从左往右逐步计算，且添加括号的数目尽可能少。只需要添加英文半角小括号这一种括号。
输入输出格式
输入：一个不带空格的算式，比如1*2*3*4，其中只有加、减、乘、除四种运算，分别用+、-、*、/四个符号来表示
输入输出样例
样例一：
输入
1+2+3*4输出
(1+2+3)*4样例二：
输入
7+8*9+10输出
(7+8)*9+10数据范围
输入的长度小于等于100 。
题解
**** Hidden Message *****
代码：
**** Hidden Message *****
奖励规则：
代码效率等方面最优，选为最佳答案，得到13鱼币+8荣誉+3贡献+1技术值
代码运行正确，奖励3鱼币
代码运行错误奖励将会折扣
仅支持使用C\C++语言编写
如果喜欢，别忘了评分{:10_281:} ：
本帖最后由 zhangjinxuan 于 2022-11-27 21:23 编辑
何必呢？
#include <bits/stdc++.h>
using namespace std;
char opts, c;
int nums, n = 1;
void solve(int l) {
bool flag = false;
if (l > 1) {
if ((opts == '*' || opts == '/') && (opts == '+' || opts == '-')) {
flag = true;
printf("(");
}
solve(l - 1);
} else printf("%d", nums);
if (flag) printf(")");
printf("%c", opts);
if (l != n) printf("%d", nums);
}
int main() {
scanf("%d", &nums);
while ((c = getchar()) != '\n'){
opts = c;
scanf("%d", &nums);
++n;
}
int st = clock();
solve(n);
int en = clock();
printf("\n用时：%dms", en - st);
return 0;
} @zhangjinxuan @编程追风梦 @陈尚涵 @元豪 @xiaosi4081 @漫星闪 @hveagle 其实我有答案，就交给别人回答吧^_^ 回复看看答案 回去睡觉啦，白天再看{:10_256:} 还忘了一个！数字确定不会爆 int，题目要说出来啊，意思是，数字的大小最大是多少，最小是多少？ 就是说我们输入一个 11111111111111111+2222222222222222222222222222222 之类的算式我们是不是就歇菜了？{:10_256:} 这......
提供个思路吧：
将从左到右运算优先级小的加括号
可以考虑用树 zhangjinxuan 发表于 2022-11-28 08:01
就是说我们输入一个 11111111111111111+2222222222222222222222222222222 之类的算式我们是不是就歇菜了？{ ...
或许得写一个大数的模拟运算？{:10_260:} 瞧瞧摸出我的逆波兰板子{:10_254:}
#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define mod 998244353
#define INF 0x3f3f3f
#define fi first
#define se second
#define it iterator
#define ins insert
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ll long long
#define ull unsigned long long
#define mem(a) memset(a,0,sizeof(a))
#define cio ios::sync_with_stdio(false)
#define gcd __gcd
ll lgcd(ll a,ll b){return b == 0? a:lgcd(b, a % b);}
int lowbit(int x){return x&(-x);}
#define T int t;scanf("%d",&t);while(t--)
#define CE cout << endl
#define C(n) cout << n << endl
#define CY cout << "YES" << endl
#define CN cout << "NO" << endl
#define Cy cout << "Yes" << endl
#define Cn cout << "No" << endl
int binaryPow(int a, int b){ // a^b%mod
int ans = 1;
while(b > 0){
if(b & 1){
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans;
}
double Calculate(double a, double b, char f)// 进行加减乘除运算
{
if(f=='+') return b+a;
if(f=='-') return b-a;
if(f=='*') return b*a;
if(f=='/') return b/a;
if(f=='^') return binaryPow(b,a);
return 0;
}
int jud(char a)// 判断优先级
{
if(a=='^') return 3;
if(a=='*'||a=='/') return 2;
if(a=='-'||a=='+') return 1;
return 0;
}
int jud1(char a)// 判断运算符
{
if(a=='+'||a=='-'||a=='*'||a=='/'||a=='^') return 1;
return 0;
}
char s;
char r;// 存储逆波兰式的结果
int k;
void ReversePolish() // 转化成逆波兰式
{
mem(r);
k = 0;
int l = strlen(s);
stack<char>q; // 临时栈（存储运算符）
for(int i = 0; i < l; i++){
if(s==' ') continue;// 去掉空格干扰
if(isdigit(s)){ // 如果是运算数
r = s;
while(isdigit(s)&&i+1<l){
r = s;
++i;
}
r = ' '; // 用空格隔开
}
if(s=='('){ // 左括号 直接入临时栈
q.push(s);
}
if(s==')'){ // 右括号 将左右括号之间运算符放进逆波兰式中
while(q.top()!='('){
r = q.top();
r = ' ';
q.pop();
}
q.pop();
}
while(jud1(s)==1){// 运算符
if(q.empty()||q.top()=='('||jud(s)>jud(q.top())){
// 栈为空，栈顶为左括号，当前运算符优先级大于栈顶运算符入栈
q.push(s);
break;
}else{
// 将栈顶运算符放进逆波兰式中
r = q.top();
r = ' ';
q.pop();
}
}
}
// 如果临时栈不为空，将剩余运算符放进逆波兰式中
while(!q.empty()){
r = q.top();
r = ' ';
q.pop();
}
cout << "Reverse Polish:";
for(int i = 0; i < k; i++) cout << r; // 输出逆波兰式
CE;
}
double Result() // 计算逆波兰式
{
stack<double>re;// 存储运算数
for(int i = 0; i < k; i++){
if(isdigit(r)){ // 运算数直接入栈
double x = r-'0';
while(r!=' '){
x = x*10+r-'0';
}
re.push(x);
}else if(jud1(r)==1){// 运算符 从栈顶取两个数运算，再将结果入栈
double x1 = re.top();
re.pop();
double x2 = re.top();
re.pop();
// cout << x1 << " " << x2 << " " << r << endl;
double x3 = Calculate(x1,x2,r);
// cout << x3 << endl;
re.push(x3);
}
}
cout << "Result:";
return re.top();
}
int main()
{
scanf("%s", s); // 读入一个四则运算
ReversePolish();// 转化成逆波兰式
double op =Result();// 计算结果
printf("%.2lf\n", op);
return 0;
}
Clamb 发表于 2022-11-28 14:17
或许得写一个大数的模拟运算？
没叫你运算，这样的话就只能运用大数读入，也麻烦不了多少 本帖最后由 lxping 于 2022-11-29 19:30 编辑
还不会正则表达式，不然应该可以更简单匹配~~{:10_266:}
old = input("请输入计算式：")
old = old.replace("*", ")&")
old = old.replace("/", ")%")
old = old.replace("&", "*")
old = old.replace("%", "/")
templist = old.split(")")
temp = ""
for i in templist[:-1]:
if "+" in i or "-" in i:
i = i + ")"
temp += i
else:
temp += i
new = temp.count(")")*"(" + temp + templist[-1]
print(new) lxping 发表于 2022-11-29 19:27
运行不过
高山 发表于 2022-11-29 19:30
运行不过
python呀~~，只会这个 lxping 发表于 2022-11-29 19:32
python呀~~，只会这个
那……没办法
我是说C或C++
页:
[1]