GZOI2011廣州NOI省選：簡易計算器 calculator 解題報告

【問題描述】相信大家都用過計算器，一般來說，計算機都可以計算簡單的加、減、乘、除這幾種運算。簡易計算器的功能和一般的計算器一樣，只是它更加簡單，只能處理整數運算，也就是說，它沒有小數點按鈕，並且它的除法運算是整除運算。現在，我們給出簡易計算器上的按鈕序列，請你編程序，模擬簡易計算器的功能，輸出最終的結果。
      【計算器組成】簡易計算器由以下按鈕組成：數字按鈕： 0 1 2 3 4 5 6 7 8 9運算按鈕： + - * /等於號按鈕：=正負轉換按鈕：+/-為了表述方便，+/- 按鈕用 F 表示 ，
 【計算器邏輯處理】
    計算器內存有3個值，M1，M2，OP，STM1為計算器的左運算值，初始值為0M2為計算器的右運算值，初始值0OP為計算器的當前運算符，初始值為空ST為狀態標記，初始值為0
 狀態裝換邏輯如下：
 ST=0 (M1/OP輸入態)：顯示值：M1
 輸入數字N ：M1=N ，轉 ST=1狀態
 輸入F ：M1=-M1，轉 ST=0狀態
 輸入運算符：OP=運算符，轉ST=2狀態
 輸入“=”：轉 ST=0狀態
 ST=1 (M1+/OP輸入態)：顯示值：M1
 輸入數字N ：如果M1>=0則 M1=M1*10+N 否則M1=M1*10-N;轉 ST=1狀態；
 輸入F ：M1=-M1，轉 ST=1狀態；
 輸入運算符：OP=運算符，轉ST=2狀態
 輸入“=”：轉 ST=0狀態
 ST=2 (OP/M2輸入態)：顯示值：M1
 輸入數字N：M2=N，轉ST=3狀態;輸入F：M2=0，轉 ST=3狀態；
 輸入運算符：OP=運算符，轉ST=2狀態
 輸入“=”：
 轉 ST=0狀態
 ST=3 (M2+/OP輸入態)：顯示值：M2
 輸入數字N：如果M2>=0則 M2=M2*10+N 否則M2=M2*10-N；轉ST=3狀態；輸入F：M2=-M2，轉 ST=3狀態；
 輸入運算符：M1=[M1][OP][M2] 的值OP=運算符；轉ST=2狀態
 輸入“=”： M1=[M1][OP][M2] 的值轉ST=0狀態
 【輸入格式】輸入只有一行，表示在計算器輸入的按鈕，長度<=100，裡面只包含如下字符 :0123456789+-*/=F輸入數據保證不會出現除以0的情況，運算過程中各個內存的值的範圍在[-10000000, 10000000] 以內

 【輸出格式】
    輸出包含一行整數，表示最後在計算器顯示的結果
 【輸入樣例】
        123=*2F-+/3+-=
        【輸出樣例】
 -82

 【分析】
字符串處理題目，由於各種狀態之間的來回跳換，所以用遞歸實現比較方便。由於數據不大，暴力的遞歸不成問題。

時間複雜度：O（length）。
            length表示字符串的長度。


 【我的代碼】
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
char str[102];
int OP;
int top=0;
int M1=0,M2=0;
int show;
int len;
int tmp;
void deal0();
void deal1();
void deal2();
void deal3();

int Getop(char op)
{
    if(op=='+')
        return 1;
    if(op=='-')
        return 2;
    if(op=='*')
        return 3;
    if(op=='/')
        return 4;
    if(op=='F')
        return 5;
    if(op=='=')
        return 6;
    return 0;
}

void check()
{
    if(top==len)
    {
        printf("%d\n",show);
        exit(0);
    }
    return;
}

void deal0()
{
    show=M1;
    check();
    tmp=0;
    if(Getop(str[top])==0)
    {
        while(Getop(str[top])==0 &&top<len)
        {
            tmp=tmp*10+str[top]-'0';
            top++;
        }
        M1=tmp;
        deal1();
        return;
    }
    if(Getop(str[top])==5)
    {
        M1=-M1;
        top++;
        deal0();
        return;
    }
    if(Getop(str[top])>=1 && Getop(str[top])<=4)
    {
        OP=Getop(str[top]);
        top++;
        deal2();
        return;
    }
    if(Getop(str[top])==6)
    {
        top++;
        deal0();
        return;
    }
}

void deal1()
{
    show=M1;
    check();
    tmp=0;
    if(Getop(str[top])==0)
    {
        while(Getop(str[top])==0 && top<len)
        {
            tmp=tmp*10+str[top]-'0';
            top++;
        }
        if(M1>=0)
            M1=M1*10+tmp;
        else
            M1=M1*10-tmp;
        deal1();
        return;
    }
    if(Getop(str[top])==5)
    {
        M1=-M1;
        top++;
        deal1();
        return;
    }
    if(Getop(str[top])>=1 && Getop(str[top])<=4)
    {
        OP=Getop(str[top]);
        top++;
        deal2();
        return;
    }
    if(Getop(str[top])==6)
    {
        top++;
        deal0();
        return;
    }
}

void deal2()
{
    show=M1;
    check();
    tmp=0;
    if(Getop(str[top])==0)
    {
        while(Getop(str[top])==0 && top<len)
        {
            tmp=tmp*10+str[top]-'0';
            top++;
        }
        M2=tmp;
        deal3();
        return;
    }
    if(Getop(str[top])==5)
    {
        M2=0;
        top++;
        deal3();
        return;
    }
    if(Getop(str[top])>=1 && Getop(str[top])<=4)
    {
        OP=Getop(str[top]);
        top++;
        deal2();
        return;
    }
    if(Getop(str[top])==6)
    {
        top++;
        deal0();
        return;
    }
}

void deal3()
{
    show=M2;
    check();
    tmp=0;
    if(Getop(str[top])==0)
    {
        while(Getop(str[top])==0 && top<len)
        {
            tmp=tmp*10+str[top]-'0';
            top++;
        }
        if(M2>=0)
            M2=M2*10+tmp;
        else
            M2=M2*10-tmp;
        deal3();
        return;
    }
    if(Getop(str[top])==5)
    {
        M2=-M2;
        top++;
        deal3();
        return;
    }
    if(Getop(str[top])>=1 && Getop(str[top])<=4)
    {
        if(OP==1)
            M1=M1+M2;
        if(OP==2)
            M1=M1-M2;
        if(OP==3)
            M1=M1*M2;
        if(OP==4)
            M1=M1/M2;
        OP=Getop(str[top]);
        top++;
        deal2();
        return;
    }
    if(Getop(str[top])==6)
    {
        top++;
        //deal0();
        if(OP==1)
            M1=M1+M2;
        if(OP==2)
            M1=M1-M2;
        if(OP==3)
            M1=M1*M2;
        if(OP==4)
            M1=M1/M2;
        deal0();
        return;
    }
}

void init()
{
    std::ios::sync_with_stdio(false);
    scanf("%s\n",&str);
    len=strlen(str);
    return;
}

int main()
{
    freopen("calculator.in","r",stdin);
    freopen("calculator.out","w",stdout);
    init();
    deal0();
    return 0;
}
 
 
 【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	20	0.000 s	275 KB	0
2	正确	20	0.000 s	275 KB	0
3	正确	20	0.000 s	275 KB	0
4	正确	20	0.000 s	275 KB	0
5	正确	20	0.000 s	275 KB	0

运行完成
运行时间 0.002 s
平均内存使用 275 KB
测试点通过状况 AAAAA
得分：100
恭喜你通过了全部测试点!