HDU-2424:Gary’s Calculator（算式计算加法和乘法）

高精度

• 题意

给你一个只含 + 和 * 的式子，计算出结果

• 输入

多组输入
每组有两行输入：第一行输入要输入的字符个数n,第二行输入n个字符（输入只有数字和‘+’‘ *’三种字符）

• 样例输入

3
100 + 600
3
20 * 4
2
500 +
5
20 + 300 * 20

• 样例输出

Case 1: 700
Case 2: 80
Case 3: Invalid Expression!
Case 4: 6020

• 分析

栈有后进先出的特点，在输入的时候判断该字符串是否是该出现的字符串，如果是那么输入合法继续进行操作，否则标记下来。当出现数字且还未出现乘号的时候该数字进栈，当出现数字且上一个符号是乘号，则栈顶元素与刚输入的数字相乘，将栈顶元素弹出，再将乘法所得结果压入栈顶，依次处理完所有的乘法，将栈内的所有数字相加，而且c++自带栈的一系列函数，所以运用栈可以更方便的计算。

• 提示

由于c++学得太烂了所以很多基本的知识都不知道 比如说string 必须用cin输入 改了老半天
数组开得比较多的时候一定要注意清空问题（由于清空问题wrong了一发，香菇）

• 代码

#include<bits/stdc++.h>
using namespace std;
string mult(string s1,string s2)///高精度乘法函数
{
    int i,j,l,a[1111],b[1111],s[2222];
    char ans[2222];
    int l1=s1.length();
    int l2=s2.length();
    memset(ans,0,sizeof(ans));
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(s,0,sizeof(s));
    for(i=0;i<l1;i++)
        a[l1-i-1]=s1[i]-'0';
    for(i=0;i<l2;i++)
        b[l2-i-1]=s2[i]-'0';
    for(i=0;i<l1;i++)
    {
        for(j=0;j<l2;j++)
    {
        s[i+j]+=a[i]*b[j];
        if(s[i+j]>=10)
        {
            s[i+j+1]+=s[i+j]/10;
            s[i+j]%=10;
        }
    }
    }
    l=l1+l2;
    for(i=l-1;i>=1;i--)
    {
        if(s[i]!=0)
            break;
        else
            l--;
    }
    for(i=l-1,j=0;i>=0;i--,j++)
        ans[j]=s[i]+'0';
    return ans;
}
string add(string s1,string s2)///高精度加法函数
{
    int l1,l2,a[2222],b[2222],sum[2222],i,l,j;
    char ans[2222];
    l1=s1.length();
    l2=s2.length();
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(sum,0,sizeof(sum));
    memset(ans,0,sizeof(ans));
    for(i=0;i<l1;i++)
        a[l1-i-1]=s1[i]-'0';
    for(i=0;i<l2;i++)
        b[l2-i-1]=s2[i]-'0';
        l=(l1>l2)?l1:l2;
    for(i=0;i<l;i++)
    {
        sum[i]+=a[i]+b[i];
        if(sum[i]>=10)
        {
            sum[i]-=10;
            sum[i+1]++;
        }
    }
    if(sum[l]>0)
        l++;
    for(i=l;i>0;i--)
    {
        if(sum[i]==0)
            l--;
        else
            break;
    }
    for(i=l,j=0;i>=0;i--,j++)
        ans[j]=sum[i]+'0';
    return ans;
}
int main()
{
    int i,j,k,n,t=0,flag=0,flag1=0;
    string a;
    string ans;
    while(~scanf("%d",&n))
    {
        stack<string>s;///string型栈的定义
        t++;
        flag=0;///输入是否合法的标记
        flag1=0;///是否遇乘法的标记
        ans.clear();///string的清空
        if(n%2==0)///当输入偶数个字符时一定是不合法的输入
        {
            while(n--)
                 cin>>a;
            cout<<"Case "<<t<<": "<<"Invalid Expression!"<<endl;
            continue;
        }
        for(i=1;i<=n;i++)
        {
            cin>>a;
            if(i%2==1&&flag==0)///当是奇数位置且目前为止输入合法
            {
                if(a[0]!='+'&&a[0]!='*')///出现数字
                {
                    if(flag1==0)///还未出现乘号
                        s.push(a);///入栈
                    else
                    {
                        flag1=0;
                        string ss=mult(s.top(),a);///乘法运算
                        s.pop();///栈顶弹出
                        s.push(ss);///乘积入栈
                    }
                }
                else
                    flag=1;///不合法的输入
            }
            if(i%2==0&&flag==0)
            {
                if(a[0]=='*')
                {
                    flag1=1;///表示遇到了乘法
                }
                else if(a[0]!='+')
                    flag=1;
            }
        }
        if(flag==1)
        {
            cout<<"Case "<<t<<": "<<"Invalid Expression!"<<endl;
            continue;
        }
        while(!s.empty())
        {
            ans=add(s.top(),ans);
            s.pop();
        }
        cout<<"Case "<<t<<": "<<ans<<endl;
    }
     return 0;
}