2014-02-17 21:31:52Morris
[UVA][五則運算、貪婪] 11890 - Calculus Simplified
Calculus Simplified
| Calculus Simplified |
We define an expression as below:
<expression> := <number> | <expression>+<expression> | <expression>-<expression> | (<expression>)
where number is defined to be an integer.
In this problem you are given an expression with all its numbers replaced with character 'x'. Then you are given a set of numbers that were actually in the expression. We know that numbers were placed in the expression in such a way that the expression evaluates to maximum possible value among all other placements. Write a program that calculates this maximum value.
Input
In the first line there is an integer T (T
100), the number of tests. Each test begins
with the expression itself. Next line is an integer N, the number of numbers in the expression. In the final
line of each test there are N integers ai (
| ai|3000). Each of these numbers should be used
in the expression exactly once. It is guaranteed that the expression can be parsed by the definition in the
problem statement and its length will not exceed 105. There are no whitespaces in the expression
and all numbers are replaced with a single 'x'. The number of 'x's in the expression is N.
Output
For each test output the maximum possible value of the expression in a single line.
Sample Input
3 x 1 2 x-x 2 -1 1 (x)+(x)-(x) 3 1 1 1
Sample Output
2 2 1
題目描述：
給一個算式中有 n 個 x 變數，這 n 個變數只能從給定的集合中挑出且不重複。
求計算後的最大值為何。
// 算式中只會有 +-()
題目解法：
先將 x 帶入 1 計算，得到有多少掛負號和正號的 x，接著對給定的數字排序，
最大的幾個帶入正號，反之帶入負號。
#include <stdio.h>
#include <stack>
#include <string.h>
#include <algorithm>
using namespace std;
int priority_op(char c) {
switch(c) {
case '(':return 0;
case '+': case '-':return 1;
case '*': case '/':return 2;
}
return -1;
}
void trans(char infix[], char buffer[]) {
int len = strlen(infix);
char *ptr = buffer;
stack<char> op;
*ptr = '\0';
for(int i = 0; i < len; i++) {
if(infix[i] == 'x') {
sprintf(ptr, "x ");
while(*ptr) ptr++;
}else {
if(infix[i] == ')') {
while(!op.empty() && op.top() != '(') {
sprintf(ptr, "%c ", op.top()), op.pop();
while(*ptr) ptr++;
}
op.pop();
} else {
if(infix[i] != '(')
while(!op.empty() && priority_op(op.top()) >= priority_op(infix[i])) {
sprintf(ptr, "%c ", op.top()), op.pop();
while(*ptr) ptr++;
}
op.push(infix[i]);
}
}
}
while(!op.empty()) {
sprintf(ptr, "%c ", op.top()), op.pop();
while(*ptr) ptr++;
}
}
long long calcPostfix(char postfix[], int xVal) {
int len = strlen(postfix);
stack<long long> stk;
for(int i = 0; i < len; i++) {
if(postfix[i] == 'x') {
stk.push(xVal);
i++;
} else {
long long a, b;
b = stk.top(), stk.pop();
a = stk.top(), stk.pop();
switch(postfix[i]) {
case '+': a = a+b;break;
case '-': a = a-b;break;
case '*': a = a*b;break;
case '/': a = a/b;break;
}
stk.push(a);
i++;
}
}
return stk.top();
}
char infix[262144], postfix[262144];
int A[262144];
int main() {
int testcase;
scanf("%d", &testcase);
while(testcase--) {
scanf("%s", &infix);
int i, n, x;
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
trans(infix, postfix);
int neg = (n - calcPostfix(postfix, 1)) / 2;
sort(A, A+n);
int sum = 0;
for(i = 0; i < neg; i++)
sum -= A[i];
for(i = neg; i < n; i++)
sum += A[i];
printf("%d\n", sum);
}
return 0;
}