Camel tradingTime Limit: 1 secondBackground
Aroud 800 A.D., El Mamum, Calif of Baghdad was presented the formula 1+2*3*4+5, which had its origin in the financial accounts of a camel transaction. The formula lacked parenthesis and was ambiguous. So, he decided to ask savants to provide him with a method to find which interpretation is the most advantageous for him, depending on whether is is buying or selling the camels.
The Problem
You are commissioned by El Mamum to write a program that determines the maximum and minimum possible interpretation of a parenthesis-less expression.
Input
The input consists of an integerN, followed byNlines, each containing an expression. Each expression is composed of at most12numbers, each ranging between1and20, and separated by the sum and product operators+and*.
Output
For each given expression, the output will echo a line with the corresponding maximal and minimal interpretations, following the format given in the sample output.
Sample input31+2*3*4+54*18+14+7*103+11+4*1*13*12*8+3*3+8Sample outputThe maximum and minimum are 81 and 30.The maximum and minimum are 1560 and 156.The maximum and minimum are 339768 and 5023.
题意：加括号求表达式的最大值和最小值、
思路：一开始看毫无头绪，但是你仔细算，表达式按照优先级顺序来算，所得的结果正好是最小值，如果按照先算加法后算乘法来算，，正好是最大值，所以剩下的就用栈来模拟完就行了。
#include <stdio.h>#include <math.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <algorithm>#include <set>#include <queue>#include <stack>#include <map>using namespace std;int main(){int T;char ch;long long a,t;long long min,max;scanf("%d",&T);while(T–) {stack<long long >minn;stack<long long >maxx;scanf("%lld",&a);minn.push(a);maxx.push(a);while((ch=getchar())!='\n') {scanf("%lld",&a);if(ch=='+') {minn.push(a);t=maxx.top();maxx.pop();t+=a;maxx.push(t);} else if(ch=='*') {maxx.push(a);t=minn.top();minn.pop();t*=a;minn.push(t);}}min=0;max=1;while(!minn.empty()) {min+=minn.top();minn.pop();}while(!maxx.empty()) {max*=maxx.top();maxx.pop();}printf("The maximum and minimum are %lld and %lld.\n",max,min);}return 0;}
同时也用对她的怀念来惩罚自己。
