字符串计算数值 模拟计算器运算

时间:2023-01-09 11:13:27

问题 D: 计算

                                                           时间限制: 1 Sec  内存限制: 128 MB
                                                                        提交: 61  解决: 27
                                                        [提交][状态][讨论版][命题人: 外部导入]

题目描述

小明在你的帮助下,破密了Ferrari设的密码门,正要往前走,突然又出现了一个密码门,门上有一个算式,其中只有“(”,“)”,“0-9”,“+”,“-”,“*”,“/”,“^”求出的值就是密码。小明数学学得不好,还需你帮他的忙。(“/”用整数除法,取商)

输入

输入共1行,为一个算式。

输出

 输出共1行,就是密码。

样例输入

1+(3+2)*(7^2+6*9)/(2)

样例输出

258

提示

 100%的数据满足:算式长度<=30 其中所有数据在2的31次方-1的范围内。

    还没学数据结构,听学过的大佬说做法是,开两个栈,一个存运算顺序,一个存数字。具体不太清楚。。。。。

   这一题我的方法是模拟人脑运算,优先寻找(),其次^,然后*/,最后+-。前面的遇到一个算一个,然后把式子在字符串中抹去,替代为刚刚算出的值,然后循环计算,直到没有数字以外的符号,就可以退出循环了。。我大体思路是这样。下面附上我的代码。

 

 

字符串计算数值 模拟计算器运算字符串计算数值 模拟计算器运算
  1 #include <iostream>
  2 #include<stack>
  3 #include<map>
  4 #include<string>
  5 using namespace std;
  6 stack<int> sta;
  7 pair <pair <int,int>,pair <int,int> > f(string& s,int l){
  8     int i=1,a,b;
  9     while(s[l-i]<='9'&&s[l-i]>='0'){
 10         if(l-i==0){
 11             break;
 12 
 13         }
 14 
 15         i++;
 16 
 17     }
 18     if(l-i!=0)
 19         i--;
 20     int start=l-i;
 21         string st=s.substr(start,i);
 22         a=atoi(st.c_str());
 23         i=1;
 24         while(s[l+i]<='9'&&s[l+i]>='0'){
 25             i++;
 26             if(l+i==s.size())
 27                 break;
 28         }
 29             st=s.substr(l+1,i-1);
 30             b=atoi(st.c_str());
 31            int en=l+i-1;
 32 
 33 
 34 
 35         pair <pair <int,int>,pair <int,int> > p(make_pair(a,b),make_pair(start,en));
 36            return p;
 37 }
 38 
 39 
 40 int val(string &s){
 41     int sum=0;
 42     int l;
 43     while((l=s.find("^"))!=string::npos){
 44         pair <pair <int,int>,pair <int,int> > p=f(s,l);
 45         int cj=1;
 46         int a=p.first.first,b=p.first.second;
 47         for(int i=0;i<b;i++)
 48             cj*=a;
 49         s.erase(p.second.first,p.second.second-p.second.first+1);
 50         s.insert(p.second.first,to_string(cj));
 51 
 52     }
 53     for(int i=0;i<s.size();i++){
 54         if(s[i]=='*'||s[i]=='/'){
 55             pair <pair <int,int>,pair <int,int> > p=f(s,i);
 56             int cj=1;
 57             int a=p.first.first,b=p.first.second;
 58             if(s[i]=='*')
 59                 cj=a*b;
 60             else
 61                 cj=a/b;
 62 
 63             s.erase(p.second.first,p.second.second-p.second.first+1);
 64             s.insert(p.second.first,to_string(cj));
 65             i=0;
 66         }
 67 
 68     }
 69     for(int i=0;i<s.size();i++){
 70         if(s[i]=='+'||s[i]=='-'){
 71             pair <pair <int,int>,pair <int,int> > p=f(s,i);
 72             int cj=1;
 73             int a=p.first.first,b=p.first.second;
 74             if(s[i]=='+')
 75                 cj=a+b;
 76             else
 77                 cj=a-b;
 78             s.erase(p.second.first,p.second.second-p.second.first+1);
 79             s.insert(p.second.first,to_string(cj));
 80             i=0;
 81         }
 82 
 83 
 84     }
 85     return atoi(s.c_str());
 86 
 87 }
 88 
 89 int main(int argc, char *argv[])
 90 {
 91     string s;
 92     int i=0;
 93     getline(cin,s);
 94     while(i!=s.size()){
 95         if(s[i]=='(')
 96             sta.push(i);
 97         if(s[i]==')'){
 98             if(!sta.empty()){
 99                 string vs=s.substr(sta.top()+1,i-sta.top()-1);
100                 string v=to_string(val(vs));
101                 s.erase(sta.top(),i-sta.top()+1);
102                 s.insert(sta.top(),v);
103                 sta.pop();
104                 i=-1;
105                 while(!sta.empty())
106                     sta.pop();
107 
108 
109                 }
110             else{
111                 printf("Wrong\n");
112                 return 0;
113             }
114        }
115         i++;
116 
117    }
118     if(!sta.empty()){
119         printf("Wrong\n");
120         return 0;
121     }
122       else{
123         int sum=val(s);
124         printf("%d\n",sum);
125 
126     }
127 
128 
129 }
View Code

  这是我的代码。

   然后我们来看看大佬的代码。。。。

 

字符串计算数值 模拟计算器运算字符串计算数值 模拟计算器运算
  1 #include<iostream>
  2 #include <stack>
  3 #include<string.h>
  4 #include<math.h>
  5 #include<cstdio>
  6 using namespace std;
  7 int mypow(int a,int b)
  8 {
  9     int c=1;
 10     for(int i=0;i<b;i++)
 11     {
 12         c=c*a;
 13     }
 14     return c;
 15 }
 16 int main()
 17 {
 18     char c;
 19     char s[300];
 20     gets(s);
 21     int w=strlen(s);
 22     for(int i=w;i>=1;i--)
 23     {
 24         s[i]=s[i-1];
 25     }
 26     s[w+1]=')';
 27     s[0]='(';
 28     s[w+2]='\0';
 29     stack<int> num;
 30     stack<char> op;
 31     for(int i=0;i<strlen(s);i++)
 32     {
 33         int f=0;
 34         int d=0;
 35         if(isdigit(s[i]))
 36         {
 37             d=s[i]-'0';
 38             f=1;
 39             while(isdigit(s[i+1]))
 40             {
 41                 f=1;
 42                 d=d*10+s[i+1]-'0';
 43                 i++;
 44             }
 45         }
 46         if(f)
 47         {
 48             num.push(d);
 49         }
 50         if(s[i]=='+'||s[i]=='-')
 51         {
 52             while(!op.empty()&&(op.top()=='*'||op.top()=='/'||op.top()=='^'||op.top()=='+'||op.top()=='-'))
 53             {
 54                 if(op.top()=='+')
 55                 {
 56                     int a=num.top();
 57                     num.pop();
 58                     int b=num.top();
 59                     num.pop();
 60                     num.push(a+b);
 61                 }
 62                 if(op.top()=='-')
 63                 {
 64                     int a=num.top();
 65                     num.pop();
 66                     int b=num.top();
 67                     num.pop();
 68                     num.push(b-a);
 69                 }
 70                 if(op.top()=='*')
 71                 {
 72                     int a=num.top();
 73                     num.pop();
 74                     int b=num.top();
 75                     num.pop();
 76                     num.push(a*b);
 77                 }
 78                 if(op.top()=='/')
 79                 {
 80                     int a=num.top();
 81                     num.pop();
 82                     int b=num.top();
 83                     num.pop();
 84                     num.push(b/a);
 85                 }
 86                 if(op.top()=='^')
 87                 {
 88                     int a=num.top();
 89                     num.pop();
 90                     int b=num.top();
 91                     num.pop();
 92                     num.push(mypow(b,a));
 93                 }
 94                 op.pop();
 95             }
 96             op.push(s[i]);
 97         }
 98         if(s[i]=='*'||s[i]=='/')
 99         {
100             while(!op.empty()&&(op.top()=='*'||op.top()=='/'||op.top()=='^'))
101             {
102                 if(op.top()=='*')
103                 {
104                     int a=num.top();
105                     num.pop();
106                     int b=num.top();
107                     num.pop();
108                     num.push(a*b);
109                 }
110                 if(op.top()=='/')
111                 {
112                     int a=num.top();
113                     num.pop();
114                     int b=num.top();
115                     num.pop();
116                     num.push(b/a);
117                 }
118                 if(op.top()=='^')
119                 {
120                     int a=num.top();
121                     num.pop();
122                     int b=num.top();
123                     num.pop();
124                     num.push(mypow(b,a));
125                 }
126                 op.pop();
127             }
128             op.push(s[i]);
129         }
130         if(s[i]=='(')
131             op.push(s[i]);
132         if(s[i]=='^')
133         {
134             while(!op.empty()&&op.top()=='^')
135             {
136                 int a=num.top();
137                 num.pop();
138                 int b=num.top();
139                 num.pop();
140                 num.push(mypow(b,a));
141                 op.pop();
142             }
143             op.push(s[i]);
144         }
145         if(s[i]==')')
146         {
147             while(op.top()!='(')
148             {
149                 if(op.top()=='*')
150                 {
151                     int a=num.top();
152                     num.pop();
153                     int b=num.top();
154                     num.pop();
155                     num.push(a*b);
156                 }
157                 if(op.top()=='/')
158                 {
159                     int a=num.top();
160                     num.pop();
161                     int b=num.top();
162                     num.pop();
163                     num.push(b/a);
164                 }
165                 if(op.top()=='^')
166                 {
167                     int a=num.top();
168                     num.pop();
169                     int b=num.top();
170                     num.pop();
171                     num.push(mypow(b,a));
172                 }
173                 if(op.top()=='+')
174                 {
175                     int a=num.top();
176                     num.pop();
177                     int b=num.top();
178                     num.pop();
179                     num.push(b+a);
180                 }
181                 if(op.top()=='-')
182                 {
183                     int a=num.top();
184                     num.pop();
185                     int b=num.top();
186                     num.pop();
187                     num.push(b-a);
188                 }
189                 op.pop();
190             }
191             op.pop();
192         }
193     }
194     cout<<num.top()<<endl;
195 }
View Code

 恩,大佬写的代码比较简洁。。。虽然我也还没仔细看。但足以看出大佬与我们的不同。。。

   

   这些代码长度都不短,是否又有更快的方法?

   有,但是就并非模拟了,考虑一下python的eval

 

字符串计算数值 模拟计算器运算字符串计算数值 模拟计算器运算
1 print(eval(input().replace('^','**').replace('/','//')))
View Code

 

一行简洁明了。