UVa 10700 - Camel trading

链接:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1641

原题：

Background

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 input

3
1+2*3*4+5
4*18+14+7*10
3+11+4*1*13*12*8+3*3+8

Sample output

The maximum and minimum are 81 and 30.
The maximum and minimum are 1560 and 156.
The maximum and minimum are 339768 and 5023.

题目大意：

给一个没有加上括号的表达式且只有+ ，*两种操作符，然后要求随便怎样添加括号，求出这个表达式的最大值和最小值.

分析与总结：

要求最大值，就让+的优先级大于*，要求最小值，就让*的优先级大于+。

计算时，用栈来做。碰到优先级大的操作符，那么就弹出两个数进行计算，再把结果压入栈，最后，在把栈中所有的数用第二优先级的操作符计算，结果就是答案。

代码：

/*
 *  UVa:  10700 - Camel trading
 *  Result: Accept
 *  Time: 0.008s
 *  Author: D_Dobule
 */
#include<cstdio>
#include<stack>
using namespace std;

stack<long long>Min;
stack<long long>Max;

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        while(!Min.empty()) Min.pop();
        while(!Max.empty()) Max.pop();

        long long a, t; 
        char ch;
        scanf("%lld",&a);
        Min.push(a);
        Max.push(a);
        while((ch=getchar())!='\n'){
            scanf("%lld",&a);
            if(ch=='+'){
                Min.push(a);
                t = Max.top();
                Max.pop();
                t += a;
                Max.push(t);
            }
            else if(ch=='*'){
                Max.push(a);
                t = Min.top();
                Min.pop();
                t *= a;
                Min.push(t);
            }
        }
        long long ans_min=0, ans_max=1;
        while(!Min.empty()){
            ans_min+=Min.top();
            Min.pop();
        }
        while(!Max.empty()){
            ans_max *= Max.top();
            Max.pop();
        }
        printf("The maximum and minimum are %lld and %lld.\n",ans_max,ans_min);
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

    
  原创http://blog.csdn.net/shuangde800，By  D_Double (转载请标明)