P1042 （C++代码）

解题思路:





注意事项:





参考代码:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
char ss1[2]={'+','-'};
char ss2[2]={'*','/'};
char ss3[1]={'^'};
int is_ss1(char c)  {for(int i=0;i<2;i++) if(c==ss1[i]) return 1; return 0;}
int is_ss2(char c)  {for(int i=0;i<2;i++) if(c==ss2[i]) return 2; return 0;}
int is_ss3(char c)  {for(int i=0;i<1;i++) if(c==ss3[i]) return 3; return 0;}
int main ()
{
    char s[30];
    char a[30];
    gets(s);
    stack<int> num;
    stack<char> ch;
    int Length=0;
    for(int i=0;i<strlen(s);i++)     //转换为后缀表达式
    {
            if(s[i]==' ') continue;
            else
            if(s[i]>='0'&&s[i]<='9')
            {
                a[Length++]=s[i];
                for(int j=i+1;j<strlen(s);j++,i++)
                if(s[j]>='0'&&s[j]<='9') a[Length++]=s[j];
                else break;
                a[Length++]=' ';      //用空格将数字隔开
            }
            else                      
            {
                if(ch.empty())  ch.push(s[i]);                
                else
                {
                    if(is_ss1(ch.top())&&(!is_ss1(s[i]))) ch.push(s[i]);
                    else if(is_ss2(ch.top())&&is_ss3(s[i])) ch.push(s[i]);
                    else
                    {
                        a[Length++]=ch.top();
                        a[Length++]=' ';
                        ch.pop();
                        while(!ch.empty())
                        {
                            if(is_ss1(ch.top())&&(!is_ss1(s[i]))) break;
                            else if(is_ss2(ch.top())&&is_ss3(s[i]))  break;
                            else
                            {
                                a[Length++]=ch.top();
                                a[Length++]=' ';
                                ch.pop();
                            }
                        }
                        ch.push(s[i]);
                    }
                }
            }
    }
    while(!ch.empty()) { a[Length++]=ch.top(); a[Length++]=' '; ch.pop();}
    //for(int i=0;i<Length;i++) cout<<a[i];
    for(int i=0;i<Length;i++)     //计算后缀表达式
    {
        int x=0,t=1;
        if(a[i]==' ') continue;
        else
        if(a[i]>='0'&&a[i]<='9')
        {
            for(int j=i;j<Length;j++,i++)
            {
                if(a[j]>='0'&&a[j]<='9')
                {
                    x=x*10+(a[j]-'0');    //******
                }
                else break;
            }
            num.push(x);
            //cout<<"..."<<x<<endl;
        }
        else
        {
            int j,k;
            j=num.top(); num.pop();
            k=num.top(); num.pop();
            switch(a[i])
            {
                case '+': k+=j;  break;
                case '-': k-=j;  break;
                case '*': k*=j;  break;
                case '/': k/=j;  break;
                case '^': int n=k; for(int m=1;m<j;m++)  n*=k; k=n;break;
            }
            //cout<<"..."<<k<<endl;
            num.push(k);
        }
    }
    cout<<num.top()<<endl;
    num.pop();
    //system("pause");
    return 0;
}