题目描述

给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

输入描述:

输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“*”，且没有括号。
所有参与运算的数字均为 0 到 之间的整数。
输入数据保证这一行只有0~9、+、*这12种字符。

输出描述:

输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于4位时，请只输出最后4位，前导0不输出。

示例1

输入
1+1*3+4
输出
8
说明
计算的结果为8，直接输出8。

示例2

输入
1+1234567890*1
输出
7891
说明
计算的结果为1234567891，输出后4位，即7891。

示例3

输入
1+1000000003*1
输出
4
说明
计算的结果为1000000004，输出后4位，即4。

备注:

对于30%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100；
对于80%的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000；
对于100%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。

解答

看到题解区里面很多人都是直接扫一两遍过程序，同样遗憾的是使用标准栈做法的题解只有一个PASCAL语言的，因此自己把C/CPP的栈做法发一下。

题目中给出的是一个常规表达式，显而易见的，我们可以通过中序转后序，然后栈处理后序，在此不讨论这种做法。

输入总共有两种类型，一种是数字，另一种是操作符（二元操作符）。

那么我们的思路就唯一了：建立两个栈，分别是操作数的栈OPND和操作符的栈ONTR。

分别用 topofSND (top of Stack Number) 和 topofSTR (top of Stack operator) 来记录其顶部。

每读入一个数，仅保留后四位。

每读入一个运算符，若优先级低于OPTR栈顶运算符的优先级，则先对栈进行计算，然后再压栈。

代码如下：

CPP（改掉头文件就是C） 

#include <cstdio>
#include <cstdlib>
int OPND[10000000],topofSND;
char OPTR[10000000];int topofSTR;
void PushSTR(char operate); // 操作符压栈
void Compute(void); // 计算
unsigned PRI(char operate); // 求运算符优先级
int main()
{
    char c;
    while(scanf("%c",&c) != EOF)
    {
        if( c >= 0x30 && c< 0x3A )OPND[topofSND] = ((10*OPND[topofSND])%10000 + (c-0x30))%10000; // 入栈过程本步完成
        if( c == '+' || c == '*')
        {
            // printf("%d\n",OPND[topofSND]);
            topofSND ++ ;
            // printf("topofSND := %d   :::: topofSTR := %d\n",topofSND,topofSTR);
            PushSTR(c);
        }
    }
    topofSND++;// 结束最后一个数的读入
    while(topofSTR>0)
    {
        Compute();
    }
    printf("%d",OPND[0]);
}
void PushSTR(char operate)
{
    while( topofSTR > 0 && PRI(operate) < PRI(OPTR[topofSTR-1]) )
    {
        Compute();
    }
    OPTR[topofSTR++] = operate;
}
unsigned PRI(char operate)
{
    if(operate == '+' || operate == '-' )return 1;
    if(operate == '*' || operate == '/' )return 2;
    return 0;
}
void Compute(void)
{
    if(topofSND < 2)
    {
        // printf("error\n");
        return ;
    }
    int temp2 = OPND[--topofSND] ;
    OPND[topofSND] = 0;
    char operate = OPTR[--topofSTR] ;
    OPTR[topofSTR] = 0;
    int temp = OPND[--topofSND] ;
    OPND[topofSND] = 0;
    // printf("topofSND := %d   :::: topofSTR := %d\n",topofSND,topofSTR);
    switch(operate)
    {
        case '+':
            {
                temp += temp2;
                // printf("%d + %d \n",temp,temp2);
                break;
            }
        case '*':
            {
                temp *= temp2;
                // printf("%d * %d \n",temp,temp2);
                break;
            }
    }
    OPND[topofSND++] = temp % 10000 ;
}


来源：RedContritio