- A+
递归
一种在方法内调用自己的思想
它会一层一层调用自己
从而实现调用一次方法
实际调用了很多次该方法
但它必须要有出口
就是到达某些条件后就退出
然后一层一层的往上退出
如果没有出口，你可以自己想一下
while(true)
我在这里用递归测试下
这种思想是不是栈的方式
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//斐波那契数列 递归实现 栈的应用 static int Fbi(int i) { Console.WriteLine("Fbi(" + i + ") 被调用(入栈)"); if (i < 2) { num++; Console.WriteLine("Fbi(" + i + ") 调用完毕（出栈）"); return i == 0 ? 0 : 1; } int a = Fbi(i - 1); int b = Fbi(i - 2); Console.WriteLine("Fbi(" + i + ") 调用完毕（出栈）"); return a + b; } |
①这里只要调用方法，就认为它入栈
②只要方法内返回数据，就认为它出栈
我们调用一下Fbi(4)
结果
可以看出完全符合栈的特性
后进先出
这里就不详细说了
毕竟没有学过编译原理，我不敢乱说
计算器（四则运算表达式求值）
使用后缀表示法（逆波兰法）
①将输入的表达式（中缀表达式）转化为计算机喜欢的后缀表达式
②利用后缀表达式得出结果
思想
中缀表达式转后缀表达式
规则：从左到右遍历中缀表达式，
①如果是数字就直接输出成为后缀表达式的一部分；
②如果是运算符号，则判断它与栈顶的优先级，如果栈为空或栈顶符号优先级低于等于它或是左括号，就将它入栈，否则输出所有优先级大于等于它的运算符号直到栈空或遇到左括号。
③如果是左括号，直接入栈。
④如果是右括号，匹配到前面的左括号，输出之间的运算符号
后缀表达式计算结果
规则：从左遍历后缀表达式
①如果是数字就入栈
②遇到运算符号，就出栈两个数
③进行运算，先出栈的数在右
理论就这么多
实现才是重点！
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Calculator { private string _expression; public MyList<string> _elements; private StackList<string> _midStack; public MyList<string> _laterString; public Calculator() { _elements = new MyList<string>(100); _midStack = new StackList<string>(100); _laterString = new MyList<string>(100); } |
①这里_expression表面意思，保存输入的表达式
②_elements这个用于顺序保存分隔好的表达式元素
因为数字可能是由好几个字符组成
而我们遍历字符串是一个个字符的处理的
所以需要匹配下区别出来数字区域
③_midStack一个功能型的中间栈用于计算出后缀表达式
再使用它和后缀表达式计算出结果
④_laterString用于顺序保存后缀表达式的元素们
⑤构造函数初始化为100的大小
因为是计算机，使用固定内存是比较实际的（个人看法）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//计算表达式 public string Cal(string expression) { this.Clear(); _expression = expression; if (!this.Match()) { Console.WriteLine("表达式非法！"); return ""; } this.TranformMidToLater(); return this.GoResult(); } |
总的计算方法思路
①在做其他操作之前先清空一下各个线性表
②把输入的表达式保存起来，匹配需要使用
③匹配出表达式的所有元素并检查表达式的合法性
④将匹配出来的表达式转换为后缀表达式
⑤利用后缀表达式计算出结果并返回
一、清空
|
1 2 3 4 5 |
private void Clear() {http://chicai.group/wp-admin/post.php?post=611&action=edit# this._elements.Clear(); this._midStack.ClearStack(); this._laterString.Clear(); } |
因为每次计算都需要使用这些线性表保存数据
为了保证上一次的计算不会影响到下一次的计算
所以清空一下，保证清清白白的
二、匹配表达式元素
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
private bool Match() { int index = 0; int exprLength = this._expression.Length; int lKuo = 0; int rKuo = 0; while (index != exprLength) { char who = this._expression[index]; char next = '\0'; if (index != exprLength-1) { next = this._expression[index + 1]; } |
这里用一个index保存遍历进度
exprLength为输入表达式的长度
记录左右括号数的lKuo和rKuo
用while循环遍历整个字符串的所有字符
取得当前字符和下一个字符（如果有，用于判断合法性）
-------------------------------------------------------
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
switch (who) { case '(': if (index == exprLength - 1 || isRightKuo(next) || isSymbol(next)) { return false; } lKuo++; //保证前面的左括号多于右括号 if (rKuo >= lKuo) { return false; } this._elements.Add("("); index++; break; |
如果当前字符是左括号（
1.判断非法情况，非法的情况为：
①（不能表达式的最后一个字符
②它下一个字符是右括号
③它的下一个字符为运算符号
2.如果合法
左括号计数器加一，并保证左括号多于右括号
3.添加左括号到表达式元素中
进度加一
-------------------------------------------------------
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
case ')': rKuo++; if (index == exprLength - 1) { this._elements.Add(")"); index++; break; } if (index == 0 || isLeftKuo(next) || isNumber(next)) { return false; } if (rKuo > lKuo) { return false; } this._elements.Add(")"); index++; break; |
如果是右括号
1.右括号计数器+1
2.判断是否为特殊情况的最后字符
是的话直接添加到表达式元素中
进度+1，退出这次循环
3.如果不是，判断合法性，非法条件为：
①）不能是第一个字符
②下一个字符为左括号
③下一个字符是数字
4.检查一下括号的左右对应个数
5.添加）括号到表达式元素中，进度+1
-------------------------------------------------------
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
default: //如果是符号类型 if (isSymbol(who)){ if (index == 0 || index == exprLength - 1) { return false; } if (isRightKuo(next) || isSymbol(next)) { return false; } this._elements.Add(who.ToString()); index++; break; } if (!isNumber(who)) { return false; } //剩下为数字，匹配数字的范围 |
剩下的就是运算符号和数字或是非法字符了
这里如果是运算符号
1.判断非法情况，非法的情况为：
①运算符为表达式的第一个字符
②运算符为最后一个字符
③下一个字符为右括号
④下一个字符为运算符
2.合法了，添加运算符到表达式元素中，进度+1，退出这次循环
-------------------------------------------------------
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
if (!isNumber(who)) { return false; } //剩下为数字，匹配数字的范围 int numberLenth = 0; bool isXiaoShu = false; while (isNumber(this._expression[index + numberLenth]) || this._expression[index + numberLenth] == '.') { if (this._expression[index + numberLenth] == '.') { if (isXiaoShu) { //不能有两个小数点以上 return false; } else { isXiaoShu = true; } } int myIndex = index + numberLenth; numberLenth++; if (myIndex == exprLength - 1) { //最后一个元素 break; } } string num = this._expression.Substring(index, numberLenth); this._elements.Add(num); index += numberLenth; //检查数字的下一个元素 if(index != exprLength) { next = this._expression[index]; } if (isLeftKuo(next)) { return false; } break; |
剩下的情况只能是数字了
1.先判断如果不是数字，那么就是非法字符了
2.用一个临时变量用于记录数字的长度（字符长度）
一个临时变量记录是否为小数
3.从当前位置向后寻找数字和小数点
计算出这个数字的字节长度
直到遇到非数字或小数点或到达表达式的最后一个字节
4.从表达式中截取出刚刚得出长度的数字
5.添加数字到表达式元素中，进度+数字的字节长度
-------------------------------------------------------
|
1 2 3 4 5 6 7 8 9 10 |
} } if (lKuo != rKuo) { return false; } return true; } |
所有的表达式字符都匹配检查完后
检查一些左括号和右括号数量是否相等
三、中缀转后缀
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
private bool TranformMidToLater() { int eleLength = this._elements.GetListLength(); if (eleLength == 0) { return false; } for (int i = 1; i <= eleLength; i++) { string element = ""; this._elements.GetElement(i, ref element); if (element == "(") { this._midStack.Push(element); continue; } if (element == ")") { //匹配前面的左括号 string e = ""; this._midStack.Pop(ref e); while (e != "(") { this._laterString.Add(e); this._midStack.Pop(ref e); } continue; } |
检查表达式元素数组是否为空
遍历表达式的每个元素
如果是左括号，直接进栈，下一个元素
如果是右括号
匹配前面的左括号
之间的运算符号都出栈加入到后缀表达式中
下一个元素
-------------------------------------------------------
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
if (element == "+" || element == "-") { if (this._midStack.GetLength() == 0) { //栈中没有元素 this._midStack.Push(element); continue; } //获取栈顶元素 string e = ""; this._midStack.GetTop(ref e); if (e == "*" || e == "/") { //栈顶符号优先级较高，输出 while (e != "(" && this._midStack.GetLength() != 0) { this._midStack.Pop(ref e); this._laterString.Add(e); this._midStack.GetTop(ref e); } } this._midStack.Push(element); continue; } |
如果是加号或者是减号
①特殊情况，如果栈为空，直接入栈
②获取栈顶元素，比较它们的优先级
③如果栈顶为*或/，优先级较高
符号依次出栈加入到后缀表达式中
知道遇到（或栈中无元素
④将加号或减号入栈
下一个元素
-------------------------------------------------------
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
if (element == "*" || element == "/") { this._midStack.Push(element); continue; } //剩下就是数字了 //直接输出 this._laterString.Add(element); //判断是否为最后一个数字 if (i == eleLength) { //将中专栈中的符号全部输出 while (this._midStack.GetLength() > 0) { string e = ""; this._midStack.Pop(ref e); this._laterString.Add(e); } } } return true; } |
如果是*或/号
直接入栈，因为+-*/中它们的优先级高
剩下的元素为数字，直接加入到后缀表达式中
如果该数字为表达式的最后一个元素
则将中转栈中剩余的符号全部出栈加入到后缀表达式中
这样子就可以得到后缀表达式了
保存在_laterString中
四、利用后缀表达式计算出结果
|
1 2 3 4 5 6 |
public string GoResult() { int Length = this._laterString.GetListLength(); if (Length <= 0) { Console.WriteLine("后缀表达式为空！"); return ""; } |
先判断后缀表达式是否为空
-------------------------------------------------------
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
string e = ""; //遍历整个后缀表达式 for (int i = 1; i <= Length; i++) { this._laterString.GetElement(i, ref e); //如果为符号，出栈两个进行计算 if (e == "+") { string termElement = ""; this._midStack.Pop(ref termElement); double e1 = Double.Parse(termElement); this._midStack.Pop(ref termElement); double e2 = Double.Parse(termElement); double result = e2 + e1; this._midStack.Push(result.ToString()); continue; } if (e == "-") { string termElement = ""; this._midStack.Pop(ref termElement); double e1 = Double.Parse(termElement); this._midStack.Pop(ref termElement); double e2 = Double.Parse(termElement); double result = e2 - e1; this._midStack.Push(result.ToString()); continue; } if (e == "*") { string termElement = ""; this._midStack.Pop(ref termElement); double e1 = Double.Parse(termElement); this._midStack.Pop(ref termElement); double e2 = Double.Parse(termElement); double result = e2 * e1; this._midStack.Push(result.ToString()); continue; } if (e == "/") { string termElement = ""; this._midStack.Pop(ref termElement); double e1 = Double.Parse(termElement); this._midStack.Pop(ref termElement); double e2 = Double.Parse(termElement); if (e1 == 0) { Console.WriteLine("除数不能为0！"); return ""; } double result = e2 / e1; this._midStack.Push(result.ToString()); continue; } |
遍历整个后缀表达式的元素
如果是符号加减乘除
则在栈中出栈两个数字（这时是字符串）
将他们转换成双进度浮点数
进行相应的运算（后出的 运算符 先出的）
得到的结果转换回字符串在加入中转栈中
-------------------------------------------------------
|
1 2 3 4 5 6 7 8 9 |
//剩下为数字，入栈 this._midStack.Push(e); } //栈中会留有一个元素，那就是结果了 string r = ""; this._midStack.Pop(ref r); return r; } |
排除了加减乘数
剩下就是数字了，直接加入中转栈
遍历完后缀表达式所有元素后
栈中会有一个元素
它就是最后计算出的结果了
取出它，返回它
任务结束
匹配时的判断方法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
//判断是否为数字 private bool isNumber(char c) { if (c >= '0' && c <= '9') { return true; } return false; } //判断是否为符号 private bool isSymbol(char c) { if (c == '+' || c == '-' || c == '*' || c == '/') { return true; } return false; } //判断是否为左括号 private bool isLeftKuo(char c) { if (c == '(') { return true; } return false; } //判断是否为右括号 private bool isRightKuo(char c) { if (c == ')') { return true; } return false; } |
测试
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
static void TestCalculator() { while (true) { string exp = Console.ReadLine(); Calculator c = new Calculator(); string result = c.Cal(exp); Console.Write("匹配元素："); string s = ""; for (int i = 1; i <= c._elements.GetListLength(); i++) { c._elements.GetElement(i, ref s); Console.Write(s + " "); } Console.WriteLine(); Console.Write("后缀表达式："); for (int i = 1; i <= c._laterString.GetListLength(); i++) { c._laterString.GetElement(i, ref s); Console.Write(s + " "); } Console.WriteLine(); Console.WriteLine("结果：" + result); Console.WriteLine(); } } |
结果
