Problem E - Camel trading

Time Limit: 1 second

Background

Aroud 800 A.D., El Mamum, Calif of Baghdad was presented the formula1+2*3*4+5, which had its origin in the financial accounts of a cameltransaction. The formula lacked parenthesis and was ambiguous. So, hedecided to ask savants to provide him with a method to find whichinterpretation is the most advantageous for him, depending on whetheris is buying or selling the camels.

The Problem

You are commissioned by El Mamum to write a program that determines themaximum and minimum possible interpretation of a parenthesis-lessexpression.

Input

The input consists of an integer N, followed by N lines, each containing an expression. Each expression iscomposed of at most 12numbers, each ranging between 1 and 20, and separatedby the sum and product operators + and *.

Output

For each given expression, the output will echo a line with thecorresponding maximal and minimal interpretations, following theformat 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.

#include <stdio.h>
#include <string.h>
int main() {
    int n;
    char str[100];
    scanf("%d ", &n);
    while(n--) {
        scanf("%s", str);
        long long smax[100], smin[100], tmp = 0;
        int i, idx1 = 0, idx2 = 0, slen = strlen(str);
        char op = '+';
        for(i = 0; i <= slen; i++) {
            if(str[i] >= '0' && str[i] <= '9') {
                tmp = tmp*10 + str[i]-'0';
            } else {
                if(op == '+') {
                    if(idx1 == 0)
                        smax[idx1++] = tmp;
                    else
                        smax[idx1-1] += tmp;
                    smin[idx2++] = tmp;
                } else {
                    if(idx2 == 0)
                        smin[idx2++] = tmp;
                    else
                        smin[idx2-1] *= tmp;
                    smax[idx1++] = tmp;
                }
                op = str[i], tmp = 0;
            }
        }
        long long amax = 1, amin = 0;
        for(i = 0; i < idx1; i++)
            amax *= smax[i];
        for(i = 0; i < idx2; i++)
            amin += smin[i];
        printf("The maximum and minimum are %lld and %lld.\n", amax, amin);
    }
    return 0;
}

您可能對以下文章有興趣

[UVA][插頭DP] 11270 - Tiling Dominoes

[UVA][DAG] 103 - Stacking Boxes

[UVA][ConvexHull] 1206 - Boundary Points

[UVA][數學、N皇后單一快速解] 10094 - Place the Guards