【C# 每日一题7】求最大的结果
DescriptionGive you a expression,you can add some parenthesis to maximize result.Example as following:1 + 2 * 3Its result is 7 in the example.But you can add a parenthesis like (1 + 2) * 3,then the result is 9,and so it is the maximization of the example.You job is to find the maximizaton of a expression. To simplify this problem,you can assume that expression contains only operator + and *,but note that integers may be negative.InputInput contains multiple test cases.Each case begin with a integer N(2<=N<=100), the number of integers of a expression.Then follows the expression.Integers and operator spearate with a single whitespace.OutputFor each case print a single line with the maximized value of the expression.Sample Input41 + 2 * 3 + -1Sample Output8
void Test{ int i = Maximize("1 + 2 * 3 + -1"); //i=8}class Node{ public int Value {get; set;} public char Operator {get; set;} public static Node operator &(Node n1, Node n2) { int result = 0; switch(n1.Operator) { case '+': result = n1.Value + n2.Value; break; case '*': result = n1.Value * n2.Value; break; } return new Node() { Value = result, Operator = n2.Operator }; }}int Maximize(string expression){ List<Node> nodes = new List<Node>(); int lastValue = 0; foreach (string s in expression.Split(' ')) { if ("+-/*".Contains(s)) { nodes.Add(new Node() { Value = lastValue, Operator = s[0]}); } else { lastValue = int.Parse(s, System.Globalization.CultureInfo.InvariantCulture); } } nodes.Add(new Node() { Value = lastValue, Operator = '+' }); Node[,] matrix = new Node[nodes.Count, nodes.Count]; for (int e = 0; e < matrix.GetLength(0); e++) { matrix[e, e] = nodes[e]; for (int s = e - 1; s >= 0; s--) { Node max = new Node(){Value = int.MinValue}; for (int split = e - 1; split >= s; split--) { Node node = matrix[s, split] & matrix[split + 1, e]; if (node.Value > max.Value) max = node; } matrix[s, e] = max; } } return matrix[0, matrix.GetLength(0)-1].Value;}
------解决方案--------------------
1 + 2 * 3 + -1
表达式本质上就是一颗树行结构，根节点是操作符，这个表达式实际上是树
+
1 -
* 1
2 3
的中序遍历，
这个问题的实质就是给你这种表达式树的后续遍历结果，在所有形成这种后续遍历的树结构中，找出和最大的那个
[解决办法]
NP复杂？？？？
[解决办法]
*/
private String Trim(String expression)
{
// 去除表达式中的空格和等号
expression = expression.Replace(" ", "").Replace("=", "");
// 补完右括号
int openCount = 0;
int closeCount = 0;
foreach (char ch in expression)
switch (ch)
{
case '(':
openCount++;
break;
case ')':
closeCount++;
break;
}
if (openCount > closeCount)
expression += new String(')', openCount - closeCount);
return expression;
}
/**
* 分离操作符和操作数
*/
private Queue<String> Split(String expression)
{
String[] oprt = { "+", "*", "/", "%", "^", "(", ")" };
//String[] oprtRegex = { @"\+", @"\*", "/", "%", @"\^", @"\(", @"\)" };
expression = Trim(expression);
//foreach (String o in oprtRegex)
// 右括号后面的减号必为操作符
expression = Regex.Replace(expression, @"(?<=\))-", " - ");
// 两个数字之间的减号亦必为操作符
expression = Regex.Replace(expression, @"(?<=\d)-(?=\d)", " - ");
// 在负号前加上空格以便分割
expression = expression.Replace("-", " -");
// 其他操作符两边都加上空格以便分割
foreach (String o in oprt)
expression = expression.Replace(o, " " + o + " ");
//Console.WriteLine(expresion);
// 将空白字符作为分割符进行切割
String[] split = Regex.Split(expression, @"\s+");
// 去除空白元素
Queue<String> result = new Queue<string>();
foreach (String str in split)
if (str.Length > 0)
result.Enqueue(str);
result.Enqueue(SIGN_CHAR);
return result;
}
/**
* 返回指定操作符的优先级
*/
static int PriorityOf(String oprt)
{
int priority = Int32.MaxValue;//error result
switch (oprt)
{
case "+":
priority = PLUS_PRIORITY;
break;
case "*":
priority = MULTIPLY_PRIORITY;
break;
case "(":
priority = OPEN_PARENTHESES_PRIORITY;
break;
case SIGN_CHAR:
priority = SIGN_PRIORITY;
break;
}
return priority;
}
}
}
结果：
[解决办法]
凑合写了一个
using System;using System.Numerics;namespace CSharpTest{ class Program { public static void Main() { int[] Items = new int[] { 8, -9, -1, 2, -7 }; BigInteger[, ,] Matrix = new BigInteger[Items.Length, Items.Length, 2]; for (int i = 0; i < Items.Length; i++) { for (int j = 0; j + i < Items.Length; j++) { int start = j; int end = i + j; if (i == 0) Matrix[start, end, 0] = Matrix[start, end, 1] = Items[start]; else { Matrix[start, end, 0] = int.MinValue; Matrix[start, end, 1] = int.MaxValue; } for (int k = start; k < end; k++) { Matrix[start, end, 0] = Max(Matrix[start, end, 0], Matrix[start, k, 0] + Matrix[k + 1, end, 0]); Matrix[start, end, 0] = Max(Matrix[start, end, 0], Matrix[start, k, 0] * Matrix[k + 1, end, 0]); Matrix[start, end, 0] = Max(Matrix[start, end, 0], Matrix[start, k, 1] * Matrix[k + 1, end, 1]); Matrix[start, end, 1] = Min(Matrix[start, end, 1], Matrix[start, k, 1] + Matrix[k + 1, end, 1]); Matrix[start, end, 1] = Min(Matrix[start, end, 1], Matrix[start, k, 0] * Matrix[k + 1, end, 1]); Matrix[start, end, 1] = Min(Matrix[start, end, 1], Matrix[start, k, 1] * Matrix[k + 1, end, 0]); } } } Console.WriteLine(Matrix[0, Items.Length - 1, 0]); Console.ReadKey(); } public static BigInteger Max(BigInteger a, BigInteger b) { return a > b ? a : b; } public static BigInteger Min(BigInteger a, BigInteger b) { return a < b ? a : b; } }}