题目链接:http://nyoj.top/problem/1272

  • 内存限制:64MB 时间限制:1000ms

题目描述

假设表达式定义为:
1. 一个十进制的正整数 X 是一个表达式。
2. 如果 X 和 Y 是 表达式，则 X+Y, X*Y 也是表达式; *优先级高于+.
3. 如果 X 和 Y 是 表达式，则 函数 Smax(X,Y)也是表达式,其值为:先分别求出 X ,Y 
值的各位数字之和，再从中选最大数。
4．如果 X 是 表达式，则 （X）也是表达式。
例如: 
表达式 12*(2+3)+Smax(333,220+280) 的值为 69。
请你编程，对给定的表达式，输出其值。 

输入描述

第一行： T 表示要计算的表达式个数 （$1 \le T \le 10$）
接下来有 T 行， 每行是一个字符串，表示待求的表达式，长度<=1000 

输出描述

对于每个表达式，输出一行，表示对应表达式的值。 

样例输入

3
12+2*3
12*(2+3)
12*(2+3)+Smax(333,220+280)

样例输出

18
60
69

解题思路

首先我们需要明白这些运算符之间的优先关系：+,*低于左括号,且高于右括号,*高于+.
首先我们建立两个栈，一个栈寄存数字，一个栈寄存运算符。
1.建立并初始化栈，将表达式起始符‘#’压入字符栈,
2.一次读入表达式中的每个字符si，循环执行3-5，直到求出整个表达式的值为止,
3.若si是数字，求出数字，并压入数字栈，读取下一字符,
4.如果si是运算符，则弹出字符栈顶的运算符，和si进行优先权比较，根据结果做不同处理.
(1)若是小于，则si压入字符栈，读取下一字符,
(2)若是大于，则从数字栈中弹出两个数，并弹出字符栈顶的运算符，进行相应运算，结果压入数字栈中,
(3)若是等于，则字符栈的栈顶元素是‘(’，且si为‘)’，这时弹出字符栈顶的(，相当于脱去括号,然后读取下一字符.

#include <bits/stdc++.h>
using namespace std;
int Smax(char *s);
char Judge(char a, char b) {
    if (a == '#')
        return '<';
    if (a == '(' && b == ')')
        return '=';
    if (b == ')')
        return '>';
    if (a == '+') {
        if (b == '*' || b == '(')
            return '<';
        else return '>';
    }
    if (a == '*') {
        if (b == '(')
            return '<';
        else return '>';
    }
    if (a == '(')
        return '<';
}
int work(int a, char c, int b) {
    switch(c) {
        case '+': return a + b;
        case '*': return a * b;
    }
}
int Chenge(int x) {
    int temp = 0;
    while (x) {
        temp += x % 10;
        x /= 10;
    }
    return temp;
}
int Cal(char *s) {
    char c;
    int a, b;
    stack <char> S;
    stack <int> num;
    S.push('#');
    for (int i = 0; s[i]; ) {
        if (s[i] == ',') {
            while (S.top() != '#') {
                if (num.size() == 1)
                    return num.top();
                a = num.top(), num.pop();
                b = num.top(), num.pop();
                c = S.top(), S.pop();
                num.push(work(a, c, b));
            }
            return num.top();
        }
        else if (s[i] == 'S') {
            int px = -1, cnt = 0, px1;
            for (int j = i; s[j] && !~px; j++) {
                if (s[j] == '(' && !cnt)
                    px1 = j;
                if (s[j] == '(')
                    cnt++;
                else if (s[j] == ')')
                    cnt--;
                if (!cnt && s[j] == ')')
                    px = j;
            }
            num.push(Smax(s + px1 + 1));
            i = px + 1;
        }
        else if (isdigit(s[i])) {
            int n, v;
            sscanf(s + i, "%d%n", &n, &v);
            num.push(n);
            i += v;
        }
        else {
            if (S.top() == '#' && s[i] == ')')
                return num.top();
            switch(Judge(S.top(), s[i])) {
                case '<': S.push(s[i]);
                    i++; break;
                case '>':
                    a = num.top(), num.pop();
                    b = num.top(), num.pop();
                    c = S.top(), S.pop();
                    num.push(work(a, c, b)); break;
                case '=': S.pop();
                    i++; break;
            }
        }
    }
    while (S.top() != '#') {
        a = num.top(), num.pop();
        b = num.top(), num.pop();
        c = S.top(), S.pop();
        num.push(work(a, c, b));
    }
    return num.top();
}
int Smax(char *s) {
    int px = 0, px2 = 0, cnt = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '(')
            cnt++;
        else if (s[i] == ')')
            cnt--;
        if (!cnt && s[i] == ',')
            px = i;
    }
    return max(Chenge(Cal(s)), Chenge(Cal(s + px + 1)));
}
int main() {
    int t;
    char s[1010];
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        printf("%d\n", Cal(s));
    }
    return 0;
}