CSU 1378 Shipura 简单模拟

上周末中南的题，当时就知道是个简单模拟题，可是一个多小时就是没写出来，代码能力啊 >.<

题意：

　　某人发明了一种程序语言，只支持一种运算">>"，和一种函数"S<>"。现在给你一个表达式，让你求值。表达式有以下几种元素：

expr : term 或者 expr+sp+">>"+sp+term

term : number 或者 "S"+sp+"<"+sp+expr+sp+">"

sp : "" 或者 " "

number : digit 或者 number+digeit

digit : "0" 或者 "1" 或者 "2" 或者 "3" 或者 "4" 或者 "5" 或者 "6" 或者 "7" 或者 "8" 或者 "9"

给你的表达式一定是一个expr，并且number总是 0到1,000,000,000之间的数。

思路：

　　这实际上就是一个计算器，只有两种运算： ">>" 这个事实上就是C语言里面的右位移，不过要注意的是，当移动的位数太大时，结果可能会向下溢出，因此要特判一下。
另外"S<>" 可以看成一种单目运算。

　　因为是计算器嘛，理所应当的想到用栈来做。两个栈，一个存放运算数，另一个存放运算符。当遇到"S"或者">>"运算的时候，直接入栈，当遇到数字的时候，先检查栈顶是否为>>运算，如果是，则从数字栈里面再弹出一个数来运算，否则入栈。当遇到"S<>"中的">"时，从数字栈中弹出一个数字进行运算。

　　如何区分 ">>"和 “>” 根据">>"后面一定会跟着数字，或者类似数字的东西。

　　另外，我先把所有的空格去掉了，觉得这样更好判断符号。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <stack>

using namespace std;

typedef long long ll;

const ll MOD = (ll)1e9+7;

const int MAXN = (int)2e6+9;

stack<ll> num;

stack<char> op;

char str[MAXN];

char str2[MAXN];

inline ll S(ll x) {

    return (x*x)%MOD;

}

void pushNum(ll x) {

    while (!op.empty() && '^'==op.top()) { //其实这个用if就好了，因为>>运算时先计算左边，所以栈中不会出现连续的>>运算

        op.pop();

        ll tmp = num.top(); num.pop();

        if (x>60) {

            tmp = 0;

            x = 0;

        }

        x = (tmp>>x);

    }

    num.push(x);

}

void slove() {

    int i = 0;

    ll tmp;

    while (true) {

        if ('\0'==str[i]) break;

        while (' '==str[i]) i++;

        if ('S'==str[i]) {

            op.push('S');

            i++;

            continue;

        }

        if ('<'==str[i]) {

            i++;

            continue;

        }

        if ('0'<=str[i]&&str[i]<='9') {

            tmp = 0;

            while ('0'<=str[i]&&str[i]<='9') {

                tmp *=10;

                tmp += str[i]-'0';

                i++;

            }

            pushNum(tmp);

            continue;

        }

        if ('>'==str[i]) {

            if ('>'==str[i+1] && ('S'==str[i+2] || ('0'<=str[i+2]&&str[i+2]<='9'))) {

                op.push('^');

                i++;

            }else if ('S'==op.top()) {

                op.pop();

                tmp = num.top(); num.pop();

                pushNum(S(tmp));

            }

            i++;

            continue;

        }

    }

    printf("%lld\n", num.top());

}

void Transform(){

    int i = 0, j = 0;

    while (true) {

        if ('\0'==str2[i]) break;

        if (' '==str2[i]) while (' '==str2[i]) i++;

        else {

            str[j++] = str2[i++];

        }

    }

    str[j] = '\0';

}

int main()

{

    #ifdef Phantom01

        freopen("CSU1378.txt", "r", stdin);

    #endif // Phantom01

    while (gets(str2)) {

        if ('#'==str2[0]&&'\0'==str2[1]) break;

        while (!num.empty()) num.pop();

        while (!op.empty()) op.pop();

        Transform();

        slove();

    }

    return 0;

}

巴特西

CSU 1378 Shipura 简单模拟

最新文章

热门文章