豆豆的数学考试计算题

豆豆 · 2019-08-05 14:01:35 · 个人记录

题目背景:

crxis是一个凶残的老师......

题目:

数学考试又到了，这次数学考试的计算题是由crxis出的，所以有点难。每道计算题都是一个只含“0”、“1”、“2”、“3”、“4”、“5”、“6”、“7”、“8”、“9”、“+”、“-”、 “*”、“/”、“^”、“(”、“)”的式子。然而，这对于还是宝宝的豆豆来说特别凶残，可是豆豆很想拿到分，于是他请求信息兼职数学巨大佬的你，帮忙编写一个计算算式的值的程序。豆豆每次都会输入一个不带等号的算式，请你输出这条算式的值。

样例:

输入样例:

2^(7*5-6*(8/2))

输出样例:

2048

样例解释:

原式=2^{(7*5-6*4)} =2^{(35-24)} =2^{11} =2048

个人题目：

豆豆的数学考试计算题

https://www.luogu.org/problem/U81547

题目分析 & 基本思想：

用栈模拟数字及数字操作符的后序遍历

代码:

//powered by Mr-Bean 

#include<bots/stdc++.h>

using namespace std;

typedef long long int LL;//用LL替换long long int(方便定义) 

LL i = 0, p = 1;//p储存栈的大小 
LL number[10001];//模拟栈空间，储存数字 
char symbol[10001];//模拟栈空间，储存数字操作符 ( + - * / ^ )
char s[456];//储存数字算术表达式 

void push(void)//将一个数字操作符入栈 
{
    p++;
    symbol[p] = s[i];
    return; 
}

void pop(void)//将一个数字操作符出栈，同时用数字栈顶及数字栈的第二个数字计算当前操作符 
{
    switch(symbol[p])//计算 
    {
        case '+': number[p-1] += number[p]; break;
        case '-': number[p-1] -= number[p]; break;
        case '*': number[p-1] *= number[p]; break;
        case '/': number[p-1] /= number[p]; break;
        case '^': number[p-1] = pow(number[p-1], number[p]); break;
    }
    p = p - 1;
    return;
}

int can(void)//判断是否开始计算一步 
{
    if((s[i]=='+' || s[i]=='-') && symbol[p]!='(')//如果上一个数字操作符是 + or - 则必须为 ( ) 才可以进行计算 
    {
        return 1;
    }
    else if((s[i]=='*' || s[i]=='/') && (symbol[p]=='*' || symbol[p]=='/' || symbol[p]=='^'))//如果上一个数字操作符是 * or / 则必须为 * / ^ 才可以进行计算 
    {
        return 1;
    }
    else//否则不可以进行计算 
    {
        return 0;
    }
}

int main()
{
    int x;
    scanf("%s", s);//输入数字算术表达式 

    s[strlen(s)] = ')';
    symbol[p] = '(';
    //给表达式套一个括号(方便加减计算的判断) 

    while(i < strlen(s))
    {
        while(s[i] == '(')
        {
            push();
            i++;
        }
        x = 0;

        while(s[i] >= '0' && s[i] <= '9')//转换成数字 
        {
            x = x * 10 + s[i] - '0';
            i++;
        }
        number[p] = x;

        do
        {
            if(s[i] == ')')
            {
                while(symbol[p] != '(')
                {
                    pop();
                }
                p--;
                number[p] = number[p + 1];
            }
            else
            {
                while(can() == 1)
                {
                    pop();
                }
                push();
            }
            i++;
        }
        while(i < strlen(s) && s[i - 1] == ')');
    }

    printf("%lld", number[0]);//答案就是栈顶数字 

    return 0;
}