本文主要是介绍表达式加括号分段，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
给出一个表达式,可以通过在不同的地方添加括号,从而改变式子的结果,比如 1+2 3,如果是(1 + 2) 3结果是9,如果是1+2*3结果是7,
现在给出一个这样的式子,保证只有乘法和加法,但是也许会出现负数.求这个式子通过不同的加括号方式,所能求得的最大结果.
解答要求
时间限制：1000ms, 内存限制：64MB
输入
第一行输入一个整数n(2<=n<=100),是所给式子的整数个数,下面包含表达式,所有整数和符号之间都会相隔一个空格,所给整数的绝对值小于1000.
输出
输出一个式子能算出的最大值(不超过int).
样例
输入样例 1 复制
4
1 + 2 * 3 + -1
输出样例 1
8
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>typedef struct TagDp {int maxValue;int minValue;
} Dp;enum {SUCCESS = 0,FAIL = 1,ZERO = 0,ONE = 1,TWO = 2,PLUS = '+',MULTI = '*'
};#define MAXITEM 100
#define MAXVALUE 2147367600int g_data[MAXITEM];
Dp g_dp[MAXITEM][MAXITEM];
char g_op[MAXITEM];
int g_dataNum;int InputData()
{int res = scanf_s("%d", &g_dataNum);if (res <= ZERO) {return FAIL;}int i = 0;while (i < g_dataNum) {res = scanf_s("%d", &g_data[i]);if (i == g_dataNum - ONE) {break;}if (res > ZERO) {res = getchar();}g_op[i] = getchar();if (g_op[i] != PLUS && g_op[i] != MULTI) {return FAIL;}++i;}return SUCCESS;
}void InitDp()
{for (int i = 0; i < g_dataNum; ++i) {for (int j = 0; j < g_dataNum; ++j) {if (i == j) {g_dp[i][i].maxValue = g_data[i];g_dp[i][i].minValue = g_data[i];} else {g_dp[i][j].maxValue = INT_MIN;g_dp[i][j].minValue = INT_MAX;}}}
}Dp GetEle(int minmin, int minmax, int maxmin, int maxmax)
{Dp result;int min1, max1;if (minmin < minmax) {min1 = minmin;max1 = minmax;} else {min1 = minmax;max1 = minmin;}int min2, max2;if (maxmin < maxmax) {min2 = maxmin;max2 = maxmax;} else {min2 = maxmax;max2 = maxmin;}result.maxValue = max1 > max2 ? max1 : max2;result.minValue = min1 < min2 ? min1 : min2;return result;
}Dp GetExpressValue(Dp left, Dp right, int op)
{Dp result;int minmin = left.minValue;int minmax = left.minValue;int maxmin = left.maxValue;int maxmax = left.maxValue;if (op == PLUS) {result.minValue = minmin + right.minValue;result.maxValue = maxmax + right.maxValue;} else {minmin *= right.minValue;minmax *= right.maxValue;maxmin *= right.minValue;maxmax *= right.maxValue;result = GetEle(minmin, minmax, maxmin, maxmax);}return result;
}int main()
{int res = InputData();if (res != SUCCESS) {return res;}InitDp();Dp temp;for (int i = g_dataNum - 1; i >= 0; --i) { // 从后往前计算，保证使用时已经计算过for (int j = i + 1; j < g_dataNum; ++j) {for (int k = i; k < j; ++k) {temp = GetExpressValue(g_dp[i][k], g_dp[k + 1][j], g_op[k]);g_dp[i][j].maxValue = temp.maxValue > g_dp[i][j].maxValue ? temp.maxValue : g_dp[i][j].maxValue;g_dp[i][j].minValue = temp.minValue < g_dp[i][j].minValue ? temp.minValue : g_dp[i][j].minValue;}}}int maxValue = g_dp[0][g_dataNum - 1].maxValue;printf("%d", maxValue);return 0;
}
这篇关于表达式加括号分段的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
