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

素颜马尾好姑娘i 2022-05-18 03:21 316阅读 0赞

> ## **问题 D: 计算** ##
> 
> 时间限制: 1 Sec 内存限制: 128 MB  
> 提交: 61 解决: 27  
> \[[提交][Link 1]\]\[[状态][Link 2]\]\[[讨论版][Link 3]\]\[命题人: 外部导入\]
> 
> ## 题目描述 ##
> 
> 小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“\*”，“/”，“^”求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法，取商)
> 
> ## 输入 ##
> 
> 输入共1行，为一个算式。
> 
> ## 输出 ##
> 
> 输出共1行，就是密码。
> 
> ## 样例输入 ##
> 
>     1+(3+2)*(7^2+6*9)/(2)
> 
> ## 样例输出 ##
> 
>     258
> 
> ## 提示 ##
> 
> 100%的数据满足：算式长度<=30 其中所有数据在2的31次方-1的范围内。

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

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

#include <iostream>
    #include<stack>
    #include<map>
    #include<string>
    using namespace std;
    stack<int> sta;
    pair <pair <int,int>,pair <int,int> > f(string& s,int l){
        int i=1,a,b;
        while(s[l-i]<='9'&&s[l-i]>='0'){
            if(l-i==0){
                break;
    
            }
    
            i++;
    
        }
        if(l-i!=0)
            i--;
        int start=l-i;
            string st=s.substr(start,i);
            a=atoi(st.c_str());
            i=1;
            while(s[l+i]<='9'&&s[l+i]>='0'){
                i++;
                if(l+i==s.size())
                    break;
            }
                st=s.substr(l+1,i-1);
                b=atoi(st.c_str());
               int en=l+i-1;
    
    
    
            pair <pair <int,int>,pair <int,int> > p(make_pair(a,b),make_pair(start,en));
               return p;
    }
    
    
    int val(string &s){
        int sum=0;
        int l;
        while((l=s.find("^"))!=string::npos){
            pair <pair <int,int>,pair <int,int> > p=f(s,l);
            int cj=1;
            int a=p.first.first,b=p.first.second;
            for(int i=0;i<b;i++)
                cj*=a;
            s.erase(p.second.first,p.second.second-p.second.first+1);
            s.insert(p.second.first,to_string(cj));
    
        }
        for(int i=0;i<s.size();i++){
            if(s[i]=='*'||s[i]=='/'){
                pair <pair <int,int>,pair <int,int> > p=f(s,i);
                int cj=1;
                int a=p.first.first,b=p.first.second;
                if(s[i]=='*')
                    cj=a*b;
                else
                    cj=a/b;
    
                s.erase(p.second.first,p.second.second-p.second.first+1);
                s.insert(p.second.first,to_string(cj));
                i=0;
            }
    
        }
        for(int i=0;i<s.size();i++){
            if(s[i]=='+'||s[i]=='-'){
                pair <pair <int,int>,pair <int,int> > p=f(s,i);
                int cj=1;
                int a=p.first.first,b=p.first.second;
                if(s[i]=='+')
                    cj=a+b;
                else
                    cj=a-b;
                s.erase(p.second.first,p.second.second-p.second.first+1);
                s.insert(p.second.first,to_string(cj));
                i=0;
            }
    
    
        }
        return atoi(s.c_str());
    
    }
    
    int main(int argc, char *argv[])
    {
        string s;
        int i=0;
        getline(cin,s);
        while(i!=s.size()){
            if(s[i]=='(')
                sta.push(i);
            if(s[i]==')'){
                if(!sta.empty()){
                    string vs=s.substr(sta.top()+1,i-sta.top()-1);
                    string v=to_string(val(vs));
                    s.erase(sta.top(),i-sta.top()+1);
                    s.insert(sta.top(),v);
                    sta.pop();
                    i=-1;
                    while(!sta.empty())
                        sta.pop();
    
    
                    }
                else{
                    printf("Wrong\n");
                    return 0;
                }
           }
            i++;
    
       }
        if(!sta.empty()){
            printf("Wrong\n");
            return 0;
        }
          else{
            int sum=val(s);
            printf("%d\n",sum);
    
        }
    
    
    }

这是我的代码。

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

#include<iostream>
    #include <stack>
    #include<string.h>
    #include<math.h>
    #include<cstdio>
    using namespace std;
    int mypow(int a,int b)
    {
    	int c=1;
    	for(int i=0;i<b;i++)
    	{
    		c=c*a;
    	}
    	return c;
    }
    int main()
    {
    	char c;
    	char s[300];
    	gets(s);
    	int w=strlen(s);
    	for(int i=w;i>=1;i--)
    	{
    		s[i]=s[i-1];
    	}
    	s[w+1]=')';
    	s[0]='(';
    	s[w+2]='\0';
    	stack<int> num;
    	stack<char> op;
    	for(int i=0;i<strlen(s);i++)
    	{
    		int f=0;
    		int d=0;
    		if(isdigit(s[i]))
    		{
    			d=s[i]-'0';
    			f=1;
    			while(isdigit(s[i+1]))
    			{
    				f=1;
    				d=d*10+s[i+1]-'0';
    				i++;
    			}
    		}
    		if(f)
    		{
    			num.push(d);
    		}
    		if(s[i]=='+'||s[i]=='-')
    		{
    			while(!op.empty()&&(op.top()=='*'||op.top()=='/'||op.top()=='^'||op.top()=='+'||op.top()=='-'))
    			{
    				if(op.top()=='+')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(a+b);
    				}
    				if(op.top()=='-')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(b-a);
    				}
    				if(op.top()=='*')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(a*b);
    				}
    				if(op.top()=='/')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(b/a);
    				}
    				if(op.top()=='^')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(mypow(b,a));
    				}
    				op.pop();
    			}
    			op.push(s[i]);
    		}
    		if(s[i]=='*'||s[i]=='/')
    		{
    			while(!op.empty()&&(op.top()=='*'||op.top()=='/'||op.top()=='^'))
    			{
    				if(op.top()=='*')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(a*b);
    				}
    				if(op.top()=='/')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(b/a);
    				}
    				if(op.top()=='^')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(mypow(b,a));
    				}
    				op.pop();
    			}
    			op.push(s[i]);
    		}
    		if(s[i]=='(')
    			op.push(s[i]);
            if(s[i]=='^')
            {
                while(!op.empty()&&op.top()=='^')
                {
                    int a=num.top();
                    num.pop();
                    int b=num.top();
                    num.pop();
                    num.push(mypow(b,a));
                    op.pop();
                }
                op.push(s[i]);
            }
    		if(s[i]==')')
    		{
    			while(op.top()!='(')
    			{
    				if(op.top()=='*')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(a*b);
    				}
    				if(op.top()=='/')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(b/a);
    				}
    				if(op.top()=='^')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(mypow(b,a));
    				}
    				if(op.top()=='+')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(b+a);
    				}
    				if(op.top()=='-')
    				{
    					int a=num.top();
    					num.pop();
    					int b=num.top();
    					num.pop();
    					num.push(b-a);
    				}
    				op.pop();
    			}
    			op.pop();
    		}
    	}
    	cout<<num.top()<<endl;
    }

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

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

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

print(eval(input().replace('^','**').replace('/','//')))

一行简洁明了。

[Link 1]: http://wlacm.com/submitpage.php?cid=1235&pid=3&langmask=262141
[Link 2]: http://wlacm.com/problemstatus.php?id=1081
[Link 3]: http://wlacm.com/bbs.php?pid=1081&cid=1235