题目描述

小明在你的帮助下，破密了 Ferrari 设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有 “0~9” ，“+” ，“-” ，“*” ，“/” , “=” ，求出的值就是密码。小明数学学得不好，还需你帮他的忙。( “/” 用整数除法)

输入格式

共 1 行，为一个算式，数字和运算符之间有空格间隔，最后以等号结束。

表达式中的运算数字为不超过 99 的正整数，数据保证不会出现除数为 0 的情况。运算符号的个数最多不超过 20。

输出格式

共 1 行，就是密码。

样例

1 + 3 + 2 * 7 + 6 * 9 / 2 =

45

23 =

23

解题思路

首先说，这典型就是栈的问题。我眼中的典型，对各位小朋友来说未必是典型的。这个没办法，你们做多了就会有感觉。这种题目，不用栈的方法来做就很难下手，用了栈的思维，一切就迎刃而解。你被卡过几次，吃过几次亏，就能积累起经验。

即便知道了这条题是栈的问题，也需要细化好几个问题：

1. 算式里既有运算符好，又有运算的数字，如果用栈来存放这些数据，怎么存放？答案是引入结构体，每一个结构体都包括 2 个成员，一个是数字，另外一个数数字后面跟着的运算符。最后一个数字是特别的，后面跟的是 "=" 。

struct Node
{
    long long num;
    char op; // 字符类型，记录运算符
}

2. 算式的运算是四则运算，只有加减乘除，运算顺序是：乘和除是同级运算，加和减也是同级运算；乘除优先于加减；同级运算是从左到右运算。所以，我们用栈来处理的时候，要与之对应。遇到乘或除，就马上运算（运算就是把栈顶元素弹出来，和下一个元素的数字运算，把运算结果和下一个元素的运算符捆绑，构成一个新的元素，压栈）。如果遇到加减，就简单压栈。所以，按照这个模式，最后就剩下加和减没有运算，这时候再来从左到右，也就是从栈底到栈顶运算。

下面举个例子

1 + 5 * 2 - 3 * 7 - 3 = ，这个式子先整理成结构体，放入数组，就是

{{1，'+'}, {5，'*'}, {2，'-'}, {3，'*'},{7，'-'}, {3，'='}}, 这些内容放进数组。

然后，对数组的内容进行处理，如果栈空或者栈顶是加减，就继续压栈，所以，{1，'+'} 和 {5，‘*’}被压栈；如果栈顶是乘除，就弹出栈顶，并和当前元素运算，例如遇到 处理到 {2，'-'} 的时候，栈顶是 {5，'*'}，所以就弹出栈顶，进行运算，把运算结果 {10,'-1'} 压栈。

一通操作之后，栈内只剩下: {{ { 1,'+'}, { 10,'-'}, {21, '-'} ,{3,'='}}

这时候，再来从左到右运算。

完善程序

#include<bits/stdc++.h>
using namespace std;
struct Node
{
	long long num;
	char op;
}s[21];
int main(){
	Node temp;
	int top=0;
	while(1)
	{
		cin>>temp.num>>temp.op;
		
		if(top>0&&s[top].op=='*') //乘
		{
			temp.num = 填空(1);
			填空(2); // 压栈
		}
		else if(top>0&&s[top].op=='/') // 除
		{
			temp.num = 填空(3);
			填空(2)；
		}
		else // 加减
			填空(2);
		
		if(temp.op=='=') break; // 遇到等号表示输入结束
	}

	//现在，栈里面不会有乘和除，只有加减运算，优先级都是一样的，从左到右运算 
	long long t = 填空(4); 
	for(int i=2;i<=top;i++) // 算式从左到右运算，也就是栈低到栈顶运算 
	{
		if(s[i-1].op=='+')
			t = 填空(5);
		else // 不是加就是减 
			t = 填空(6);
	}

	printf("%lld",t);

    return 0;
}

填空(1)：{{ input(1) }}

填空(2)：{{ input(2) }}

填空(3)：{{ input(3) }}

填空(4)：{{ input(4) }}

填空(5)：{{ input(5) }}

填空(6)：{{ input(6) }}