- A+
在11月的下雪天，小悦身处于温暖的办公室中，窗外的雪花在灯光下翩翩起舞。她盯着电脑屏幕，不经意间，一个熟悉的身影从办公室门口处经过，吸引了她的目光。那个人看上去很像是一个女孩，名叫苏菲，是她在大学时期遇到的国外交换生。
小悦的心跳加速，她有些不敢相信自己的眼睛。在她的记忆中，苏菲是一个温柔、聪明且乐于助人的女孩。她们曾经一起上过计算机科学课，苏菲对数学和编程的热爱给小悦留下了深刻的印象。在课程中，苏菲表现出了非凡的编程天赋和扎实的技术功底，她的编程能力让小悦敬佩不已。
小悦忍不住站起来，快步走向那个人。她轻轻地拍了拍她的肩膀，问道：“苏菲？”
那个女孩转过身来，露出了一张熟悉的面孔。她的眼睛闪烁着聪慧的光芒，嘴角挂着一抹微笑。她惊喜地喊道：“小悦？”
两人紧紧地拥抱在一起，重逢的喜悦让她们感到温暖。她们来到楼下的咖啡厅，开始回忆起大学时期的时光，谈论着彼此的生活和工作。
小悦感到非常惊喜，没想到苏菲会来到她的办公楼。苏菲也并不知道小悦在这里工作。或许是命运的安排，让她们再次相遇。小悦心想，一定要好好和苏菲聊聊天，畅谈彼此的近况，重温那段美好的大学时光。
小悦想起了那次计算机科学课的上机考试。她需要实现一个计算器表达式算法。小悦在考试前尝试着自己实现了一个多项式解析式算法，但是效果并不甚理想。这个问题让她感到很困惑，不知道如何着手。就在这时，苏菲主动帮助了她。
苏菲耐心地解释了如何分析问题、拆分令牌、使用逆波兰表达式算法进行计算，以及如何使用栈来处理后缀表达式。她的思路清晰、有条理，让小悦瞬间明白了问题的解决方法。
在苏菲的帮助下，小悦成功地解决了问题，并且在考试中取得了优异的成绩。她一直感激苏菲的帮助和鼓励。
回忆起那段经历，小悦不禁感慨万分。她对苏菲说：“谢谢你，苏菲。你的帮助和支持让我变得更加自信和勇敢。”
苏菲微笑着说：“我们是朋友，小悦。无论何时何地，我都会尽力帮助你。”
她们聊了很久，谈论着过去的点点滴滴和现在的变化。毕业后，苏菲选择继续深造，攻读计算机科学硕博学位。在国外留学期间，她积累了丰富的经验和技能，志向是成为一名计算机科学家。然而，尽管小悦和苏菲在大学时期形影不离，但毕业后两人便各奔东西，相距太远，渐渐失去了联系。她们还计划着再次回到校园，去湖心岛看看那个曾经给她们带来无限回忆的地方。
在分别前，小悦紧紧地拥抱了苏菲一次。她心里默默地想：谢谢你，苏菲，谢谢你陪我度过了那段美好的时光。我会永远珍惜这份友谊。
随着时间的推移，虽然小悦和苏菲的联系越来越少。但是她们的友谊和回忆永远留在彼此的心中。在这个下雪的日子里，小悦重新与苏菲相遇，让她回忆起了那些青葱校园岁月和湖心岛的甜蜜时光。她感到无比幸福和感激，因为她知道这些美好的回忆将永远伴随着她走过人生的旅程。即使未来还有更多的挑战等待着她，小悦也相信自己的能力能够克服一切困难。
当时小悦和苏菲面对的考试题目为：要求计算一个包含数字和运算符的字符串的结果，包括加减乘除和幂运算，还有括号。数字可以是整数或小数，字符串中可以有空格。要求处理字符串中的所有运算符和数字，并计算出最终的结果。
示例：3 * (4 + (2 / 3) * 6 - 5)=9;
123 -( 4^ ( 3 - 1) * 8 - 8 /( 1 + 1 ) *(3 -1) )=3;
算法实现1:
1 using System; 2 using System.Collections.Generic; 3 4 public static class Edm { 5 6 public static double calculate(string input) 7 { 8 // 从输入中移除空格 9 input = input.Replace(" ", ""); 10 11 // 将输入转换为令牌列表 12 List<string> tokens = new List<string>(); 13 string currentToken = ""; 14 foreach (char c in input) { 15 if (char.IsDigit(c) || c == '.') { // 如果字符是数字或小数点 16 currentToken += c; // 将字符添加到当前令牌中 17 } else { 18 if (currentToken != "") { // 如果当前令牌不为空 19 tokens.Add(currentToken); // 将当前令牌添加到令牌列表中 20 currentToken = ""; // 重置当前令牌 21 } 22 tokens.Add(c.ToString()); // 将字符转换为字符串并添加到令牌列表中 23 } 24 } 25 if (currentToken != "") { // 如果当前令牌不为空 26 tokens.Add(currentToken); // 将当前令牌添加到令牌列表中 27 } 28 29 // 使用逆波兰算法评估令牌 30 Stack<string> operatorStack = new Stack<string>(); // 操作符栈 31 Queue<string> outputQueue = new Queue<string>(); // 输出队列 32 foreach (string token in tokens) { 33 if (double.TryParse(token, out double num)) { // 如果令牌可以转换为双精度浮点数 34 outputQueue.Enqueue(num.ToString()); // 将数字转换为字符串并添加到输出队列中 35 } else if (IsOperator(token)) { // 如果令牌是操作符 36 while (operatorStack.Count > 0 && IsOperator(operatorStack.Peek()) && GetPrecedence(token) <= GetPrecedence(operatorStack.Peek())) { 37 outputQueue.Enqueue(operatorStack.Pop()); // 将操作符栈中的操作符弹出并添加到输出队列中 38 } 39 operatorStack.Push(token); // 将操作符添加到操作符栈中 40 } else if (token == "(") { // 如果令牌是左括号 41 operatorStack.Push(token); // 将左括号添加到操作符栈中 42 } else if (token == ")") { // 如果令牌是右括号 43 while (operatorStack.Count > 0 && operatorStack.Peek() != "(") { 44 outputQueue.Enqueue(operatorStack.Pop()); // 将操作符栈中的操作符弹出并添加到输出队列中 45 } 46 if (operatorStack.Count == 0) { 47 throw new Exception("Mismatched parentheses"); // 抛出异常，提示括号不匹配 48 } 49 operatorStack.Pop(); // 弹出左括号 50 } else { 51 throw new Exception("Invalid token: " + token); // 抛出异常，提示令牌无效 52 } 53 } 54 while (operatorStack.Count > 0) { 55 if (operatorStack.Peek() == "(") { 56 throw new Exception("Mismatched parentheses"); // 抛出异常，提示括号不匹配 57 } 58 outputQueue.Enqueue(operatorStack.Pop()); // 将操作符栈中的操作符弹出并添加到输出队列中 59 } 60 61 // 评估后缀表达式 62 Stack<double> operandStack = new Stack<double>(); // 操作数栈 63 foreach (string token in outputQueue) { 64 if (double.TryParse(token, out double num)) { // 如果令牌可以转换为双精度浮点数 65 operandStack.Push(num); // 将数字添加到操作数栈中 66 } else if (IsOperator(token)) { // 如果令牌是操作符 67 double b = operandStack.Pop(); 68 double a = operandStack.Pop(); 69 double result = EvaluateOperator(token, a, b); // 计算操作符对应的结果 70 operandStack.Push(result); // 将计算结果压入操作数栈中 71 } else { 72 throw new Exception("Invalid token: " + token); // 抛出异常，提示令牌无效 73 } 74 } 75 if (operandStack.Count != 1) { 76 throw new Exception("Invalid expression"); // 抛出异常，提示表达式无效 77 } 78 return operandStack.Pop(); // 返回操作数栈中唯一的元素作为计算结果 79 } 80 81 static bool IsOperator(string token) { 82 return token == "+" || token == "-" || token == "*" || token == "/" || token == "^"; // 判断一个字符串是否为操作符（+、-、*、/、^） 83 } 84 85 static int GetPrecedence(string op) {// 获取操作符优先级 86 if (op == "^") { 87 return 3; 88 } else if (op == "*" || op == "/") { 89 return 2; 90 } else if (op == "+" || op == "-") { 91 return 1; 92 } else { 93 return 0; 94 } 95 } 96 97 // 计算两个操作数和一个操作符的结果 98 static double EvaluateOperator(string op, double a, double b) { 99 if (op == "+") { 100 return a + b; 101 } else if (op == "-") { 102 return a - b; 103 } else if (op == "*") { 104 return a * b; 105 } else if (op == "/") { 106 return a / b; 107 } else if (op == "^") { 108 return Math.Pow(a, b); 109 } else { 110 throw new Exception("Invalid operator: " + op); 111 } 112 } 113 }
这段代码实现了一个表达式计算器，能够接受包含基本数学运算的字符串表达式，并返回计算结果。
-
导入了System和System.Collections.Generic命名空间，用于使用标准的数据结构和功能。
-
定义了一个静态类Edm，其中包含一个名为calculate的静态方法，该方法接受一个字符串输入并返回一个双精度浮点数。
-
calculate方法首先去除输入中的空格，然后将输入转换为一个令牌列表（tokens）。
-
使用逆波兰算法（shunting yard algorithm）对令牌进行评估。它使用了操作符栈（operatorStack）和输出队列（outputQueue）来对表达式进行处理。
-
在这段代码中，我们使用了操作符栈和输出队列来处理给定的令牌（tokens）。
- 首先，我们遍历令牌数组，对每个令牌进行处理。
- 如果令牌是一个数字，我们将其转换为字符串并添加到输出队列中。
- 如果令牌是一个操作符，我们需要根据操作符的优先级来决定其在输出队列中的位置。我们将当前操作符与操作符栈顶的操作符进行比较，如果当前操作符的优先级小于或等于栈顶操作符的优先级，则将栈顶操作符弹出并添加到输出队列中，直到满足条件为止，然后将当前操作符压入操作符栈中。
- 如果令牌是左括号，我们直接将其压入操作符栈中。
- 如果令牌是右括号，我们需要将操作符栈中的操作符弹出并添加到输出队列中，直到遇到左括号为止。如果在弹出操作符时，操作符栈为空，或者没有遇到左括号，就会抛出异常提示括号不匹配。
- 如果令牌不是数字、操作符、左括号或右括号，则抛出异常提示令牌无效。
- 最后，处理完所有令牌后，将操作符栈中剩余的操作符依次弹出并添加到输出队列中。如果在此过程中遇到左括号，也会抛出异常提示括号不匹配。
这样，我们可以将中缀表达式转换为后缀表达式，并且在这个过程中处理了操作符的优先级和括号的匹配关系。
-
对后缀表达式进行评估。这部分代码使用了操作数栈（operandStack）来计算后缀表达式的值。
-
评估后缀表达式的详细解释：
- 创建一个空的操作数栈，用于存储操作数。
- 遍历后缀表达式中的每个令牌。
- 如果令牌可以转换为双精度浮点数，则将其压入操作数栈中。
- 如果令牌是操作符，则从操作数栈中弹出两个操作数（假设为a和b），然后根据该操作符对这两个操作数进行计算，得到结果。
- 将计算得到的结果压入操作数栈中。
- 如果令牌不是数字也不是操作符，则抛出异常提示令牌无效。
- 完成对所有令牌的处理后，操作数栈中应该只剩下一个元素，即为最终的计算结果。如果操作数栈中的元素不止一个，说明表达式无效，抛出异常。
-
IsOperator方法用于检查一个字符串是否为操作符（+、-、*、/、^）。
-
GetPrecedence方法用于获取操作符的优先级。
-
EvaluateOperator方法用于计算两个操作数和一个操作符的结果。
逆波兰表达式算法由荷兰计算机科学家Edsger Dijkstra在1960年代实现，它也是ALGOL60语言的基础算法，因为在ALGOL60上做出原理性贡献，Dijkstra获得了1972年的图灵奖。而该算法的名称来源于其发明者，波兰数学家Jan Łukasiewicz由1929年提出此数学方法。
逆波兰表达式算法的数学原理可以通过栈的数据结构来解释。我们以中缀表达式 "3 + 4 * 2" 为例进行解释。
- 遍历中缀表达式中的每个令牌（数字、操作符）。
- 如果令牌是数字，则直接将其添加到输出队列中。
- 如果令牌是操作符： a. 如果操作符栈为空，或者操作符栈顶的操作符优先级小于当前操作符，则将当前操作符压入操作符栈中。 b. 如果操作符栈顶的操作符优先级大于等于当前操作符，则将操作符栈顶的操作符弹出并添加到输出队列中，直到满足条件为止，然后将当前操作符压入操作符栈中。
- 处理完所有令牌后，将操作符栈中剩余的操作符依次弹出并添加到输出队列中。
以中缀表达式 "3 + 4 * 2" 为例，通过上述步骤，我们可以将中缀表达式转换为后缀表达式 "3 4 2 * +"。
中缀表达式转换为后缀表达式的过程是为了更方便地让计算机进行数学表达式的计算。后缀表达式（也称为逆波兰表达式）具有以下优点：
-
没有括号：后缀表达式不需要括号来表示运算的优先级，因此避免了括号所带来的歧义和复杂性。
-
易于计算：后缀表达式的计算可以通过简单的迭代算法来实现，不需要递归或者栈来保存中间结果，这使得计算更加高效。
对于后缀表达式 "3 4 2 * +"，我们可以按照以下步骤进行计算：
- 从左到右扫描后缀表达式，遇到操作数就将其压入栈中。
- 遇到操作符时，从栈中弹出相应数量的操作数进行计算，并将计算结果压入栈中。
- 最终栈中剩下的元素就是整个表达式的计算结果。
对于后缀表达式 "3 4 2 * +"，计算过程如下：
- 遇到 "3"，压入栈中
- 遇到 "4"，压入栈中
- 遇到 "2"，压入栈中
- 遇到 "*"，弹出栈顶的两个元素（4和2），计算结果为8，将结果压入栈中
- 遇到 "+"，弹出栈顶的两个元素（3和8），计算结果为11，将结果压入栈中
- 最终栈中剩下的唯一元素就是整个表达式的计算结果，即11。
因此，后缀表达式的转换和计算可以使数学表达式在计算机中的处理更加简单和高效。
逆波兰表达式算法之所以受到广泛应用，是因为它能够有效地解决中缀表达式计算的问题。中缀表达式需要使用括号来确定操作符的优先级，而逆波兰表达式则不需要，因为它使用后缀表示法，操作符的优先级可以通过操作符的顺序来确定。
逆波兰表达式算法在计算器、编译器、解释器等领域都有广泛应用。在计算器中，用户输入的数学算式，即中缀表达式通常需要转换为逆波兰表达式才能进行计算。在编译器和sql解释器中，逆波兰表达式算法可以用于计算sql表达式的值，以及将sql表达式转换为可执行代码。
算法实现2：
1 public static double calculate(string s){ 2 s=s.Replace(" ",""); 3 if (Regex.Match(s,"^[(][\d\.\+\-\*/\^]+[)]$").Success) s=Regex.Replace(s,"^[(]|[)]$",""); 4 if (Regex.Match(s,"^-?[\d\.]+$").Success) return double.Parse(s);//检测到单个的正负数字，直接返回值 5 if (Regex.Match(s,"^\d[\d+-\.]+$").Success) return Regex.Matches(s,"-[\d\.]+|(?<=^|[+])[\d\.]+").OfType<Match>().Sum(x=>double.Parse(x.Value)); //检测到只包含连续+-符号的算式，返回其运算值 6 if (Regex.Match(s,"^[\d\.]+[*/\^][\d\.]+$").Success) { //检测到两个数的乘除次方，返回其运算值 7 var tmp=Regex.Split(s,"[*/\^]").Select(double.Parse).ToArray(); 8 return s.Contains('*') ? tmp[0]*tmp[1] : s.Contains('/') ? tmp[0]/tmp[1] : Math.Pow(tmp[0],tmp[1]); 9 } 10 if (s.Contains('(')) { //检测到括号，先运算一个括号单元，然后递归 11 var tmp=Regex.Match(s,"[(][\d\.\+\-\*/\^]+[)]").Value; 12 return calculate(s.Substring(0,s.IndexOf(tmp))+calculate(tmp)+s.Substring(s.IndexOf(tmp)+tmp.Length)); 13 } 14 if (s.Contains('^')) { //检测次方符号，优先运算 15 var tmp=Regex.Match(s,"[\d\.]+[\^][\d\.]+").Value; 16 return calculate(s.Substring(0,s.IndexOf(tmp))+calculate(tmp)+s.Substring(s.IndexOf(tmp)+tmp.Length)); 17 } 18 if (s.Contains('*')||s.Contains('/')) { //检测乘除符号，优先运算 19 var tmp=Regex.Match(s,"[\d\.]+[\*/][\d\.]+").Value; 20 return calculate(s.Substring(0,s.IndexOf(tmp))+calculate(tmp)+s.Substring(s.IndexOf(tmp)+tmp.Length)); 21 } 22 return 0; 23 }
算法2是一个用于计算数学表达式的算法，使用了正则表达式和递归的思想，以及一些基本的操作符处理和字符串处理方法。这种类型的算法通常用于计算机科学和编程中，以便对数学表达式进行求值。
在工作之余，小悦回想起大学时期的那次考试。当时，她运用逆波兰表达式算法成功解决了算式计算器问题。而现在，凭借着工作经验的积累，她采用自己设计的方法——正则表达式和递归算法。
小悦运用正则表达式的强大功能，将输入的算式进行精准的解析和拆分。她巧妙地运用正则表达式的分组和捕获功能，将算式拆分为一个个独立的子表达式。然后，她利用递归算法的特性，对这些子表达式进行递归计算。这种方法的优点在于，它能够处理包含括号、运算符优先级等复杂元素在内的算式，同时还能保证计算过程的灵活性和高效性。
但算法2对于更复杂的脚本语言解释器来说，对于更复杂的表达式，比如函数调用、变量赋值等，就无法处理，可能需要考虑更多的功能和错误处理机制。如果需要实现一个更完整的脚本解释器，还是需要通过算法1进行扩展。
算法1和算法2的比较如下：
算法1优点：
- 逆波兰表达式算法不需要使用括号，因此可以减少括号匹配的复杂性。
- 逆波兰表达式算法可以直接利用栈结构进行计算，简化了中缀表达式转换为后缀表达式的过程。
- 逆波兰表达式算法可以用于解释各种类型的语言和数据格式，从而实现各种解释器。这些解释器可以用于实现各种应用，例如命令行工具、页面脚本语言、配置文件解析器、sql数据库查询解析器等。
算法1缺点：
- 中缀表达式转换为后缀表达式的过程可能较为复杂，需要额外的转换步骤。
- 逆波兰表达式算法需要额外的数据结构（栈）来进行计算，可能需要更多的内存空间。
算法2优点：
- 算法2可以直接对中缀表达式进行递归计算，不需要额外的转换步骤。
- 算法2可以直接处理括号、乘除次方等运算符，逻辑相对清晰。
算法2缺点：
- 算法2中使用了正则表达式进行匹配，可能在处理复杂表达式时效率较低。
- 算法2在处理嵌套括号的情况时可能需要多次递归计算，效率较低。
- 算法2对于更复杂的脚本语言解释器来说，不容易扩展和优化。
综合来看，算法1在处理简单表达式时可能更加高效，而算法2在处理复杂数学表达式时可能更加直观和易于理解。具体选择哪种算法取决于实际需求和对算法的偏好。
测试用例：
1 using NUnit.Framework; 2 using System; 3 [TestFixture] 4 public class CalculatorTest 5 { 6 public bool close(double a, double b) 7 { 8 if (Math.Abs(a-b)<0.000000001) return true; 9 return false; 10 } 11 [Test] 12 public void EasyTests() 13 { 14 Assert.AreEqual(true, close(Edm.calculate("3 + 5"), 8)); 15 Assert.AreEqual(true, close(Edm.calculate("5 + 41"), 46)); 16 Assert.AreEqual(true, close(Edm.calculate("5 - 3"), 2)); 17 Assert.AreEqual(true, close(Edm.calculate("5 - 5"), 0)); 18 Assert.AreEqual(true, close(Edm.calculate("3 * 5"), 15)); 19 Assert.AreEqual(true, close(Edm.calculate("2 * 23"), 46)); 20 Assert.AreEqual(true, close(Edm.calculate("123 / 3"), 41)); 21 Assert.AreEqual(true, close(Edm.calculate("22 / 1"), 22)); 22 } 23 24 [Test] 25 public void MediumTests() 26 { 27 Assert.AreEqual(true, close(Edm.calculate("3 + 5 * 2"), 13)); 28 Assert.AreEqual(true, close(Edm.calculate("5 - 3 * 8 / 8"), 2)); 29 Assert.AreEqual(true, close(Edm.calculate("6*(2 + 3)"), 30)); 30 Assert.AreEqual(true, close(Edm.calculate("2 ^ 5"), 32)); 31 Assert.AreEqual(true, close(Edm.calculate("5 ^0"), 1)); 32 Assert.AreEqual(true, close(Edm.calculate("23.2- 15.2"), 8)); 33 Assert.AreEqual(true, close(Edm.calculate("22 / 5"), 22.0/5)); 34 } 35 36 [Test] 37 public void HardTests() 38 { 39 Assert.AreEqual(true, close(Edm.calculate("3 * (4 + (2 / 3) * 6 - 5)"), 9)); 40 Assert.AreEqual(true, close(Edm.calculate("123 -( 4^ ( 3 - 1) * 8 - 8 /( 1 + 1 ) *(3 -1) )"), 3)); 41 Assert.AreEqual(true, close(Edm.calculate("4 + 2 * ( (226 - (5 * 3) ^ 2) ^ 2 + (10.7 - 7.4) ^ 2 - 6.89)"),14)); 42 Assert.AreEqual(true, close(Edm.calculate(" (226 - (5 * 3) ^ 2) ^ 2"),1)); 43 } 44 45 [Test] 46 public void RandomTest() //some really simple random tests just to get this older kata out of beta (@smile67, 26.10.2017) 47 { 48 string [] f=new string []{"a * b -c","a + b/ (b + c)","(a + c+ b) * b *a"}; 49 Random rnd = new Random(); 50 for (int i=1;i<51;i++) { 51 int r= rnd.Next(0,3), a= rnd.Next(0,100), b= rnd.Next(0,100), c= rnd.Next(0,100); 52 string t=f[r].Replace("a",a+"").Replace("b",b+"").Replace("c",c+""); 53 double s1=Edm.calculate(t), s2=calculate2(t); 54 Console.WriteLine(i+". Tested for: "+t+", Expected: "+s2+", Got: "+s1); 55 Assert.AreEqual(true, close(s1, s2)); 56 } 57 } 58 59 //my old solution (no recursion, so only one function name/call to change - i'm lazy;-)) 60 static int[] priority = new int[11] { 1, 2, 0, -1, -1, 1, 0, 0, 0, 0, 1 }; 61 static double[] numStack = new double[256]; 62 static char[] buffer = new char[256]; 63 64 public static double calculate2 (string input) 65 { 66 input = input.Replace(" ", "").Replace("^","&")+")"; 67 string number = ""; 68 char ch, chBefore = '('; 69 int prio, numCount = 0, opCount = 1; 70 buffer[0] = '('; buffer[1] = '('; 71 for (int i = 0; i < input.Length; i++) 72 { 73 if (((ch = input[i]) >= '0') || (ch == '.')) number += ch; 74 else 75 { 76 if (chBefore < '0') if (chBefore != ')') if (ch == '-') ch = '%'; 77 if (number.Length > 0) { numStack[++numCount] = Convert.ToDouble(number); number = ""; } 78 if (ch > '(') 79 { 80 prio = priority[ch - 37]; 81 while (opCount > 0 && prio <= priority[buffer[opCount] - 37]) 82 { 83 --numCount; 84 switch (buffer[opCount]) 85 { 86 case '+': numStack[numCount] = numStack[numCount] + numStack[numCount + 1]; break; 87 case '-': numStack[numCount] = numStack[numCount] - numStack[numCount + 1]; break; 88 case '*': numStack[numCount] = numStack[numCount] * numStack[numCount + 1]; break; 89 case '/': numStack[numCount] = numStack[numCount] / numStack[numCount + 1]; break; 90 case '&': numStack[numCount] = Math.Pow(numStack[numCount], numStack[numCount + 1]); break; 91 case '%': numCount++; numStack[numCount] = -numStack[numCount]; break; 92 case '(': numCount++; prio = 5; break; 93 } 94 opCount--; 95 } 96 } 97 if (ch != ')') buffer[++opCount] = ch; 98 } 99 chBefore = ch; 100 } 101 return numStack[1]; 102 } 103 104 }
// 返回操作数栈中唯一的元素作为计算结果
