C#数据结构与算法系列（十）：中缀表达式转后缀表达式
2024-09-06 05:08:55
1.具体步骤
1）初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2）从左至右扫描中缀表达式；
3）遇到操作数时，将其压s2；
4）遇到运算符时，比较其与s1栈顶运算符的优先级：
（1）如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
（2）否则，若优先级比栈顶运算符的高，也将运算符压入s1；
（3）否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
5）遇到括号时：
（1）如果是左括号“(”，则直接压入s1
（2）如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6）重复步骤2至5，直到表达式的最右边
7）将s1中剩余的运算符依次弹出并压入s2
8）依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
2.思路分析
3.代码实现
/// <summary>
/// 字符串转中缀表达式的List
/// </summary>
/// <param name="expression"></param>
/// <returns></returns>
public static List<string> ToInfixExpression(string expression)
{
List<string> list = new List<string>(); int index = ; string str = ""; do
{ //48-57ASCII码代表的是0-9 如果不是0-9直接入链表
if (expression[index] < || expression[index] > )//ascii编码
{
list.Add("" + expression[index]); index++;
}
else
{
str = ""; //多位数判断
while (index < expression.Length && expression[index] >= && expression[index] <= )
{ str += expression[index]; index++;
} list.Add(str);
} } while (index < expression.Length); return list;
}
/// <summary>
/// 中缀转后缀
/// </summary>
/// <param name="expression"></param>
/// <returns></returns>
public static List<string> ParseSuffixExpression(List<string> expression)
{
//存储中间结果
List<string> list = new List<string>();
//符号栈
Stack<string> stack = new Stack<string>(); foreach (var item in expression)
{
//多位数判断 如果是数字直接加入list
if (Regex.IsMatch(item, "\\d+"))
{
list.Add(item);
}
//如果是左括号，直接入符号栈
else if (item.Equals("("))
{
stack.Push(item);
}
//如果是右括号
else if (item.Equals(")"))
{
//依次弹出stack栈顶的运算符，并存入list,直到遇到左括号为止
while (!stack.Peek().Equals("("))
{
list.Add(stack.Pop());
}
//将(也出栈
stack.Pop();
}
//如果是*/+-
else
{
//循环判断item的优先级小于或者等于stack栈顶运算符，将stack栈顶的运算符出栈并加入到list中
while (stack.Count != && Operation.GetValue(stack.Peek()) >= Operation.GetValue(item))
{
list.Add(stack.Pop());
}
//将item入栈
stack.Push(item);
}
} //将stack剩余的运算符依次入list
while (stack.Count!=)
{
list.Add(stack.Pop());
} return list;
}
public class Operation
{
private static int ADD = ;
private static int SUB = ;
private static int MUL = ;
private static int DIV = ; public static int GetValue(string operation)
{
int result = ; switch (operation)
{
case "+":
result = ADD;
break;
case "-":
result = SUB;
break;
case "*":
result = MUL;
break;
case "/":
result = DIV;
break;
default:
// Console.WriteLine("不存在该运算符");
break;
} return result;
}
}
/// <summary>
/// 计算
/// </summary>
/// <param name="list"></param>
/// <returns></returns>
public static int Calculate(List<string> list)
{
//创建栈
Stack<string> stack = new Stack<string>(); //循环遍历
list.ForEach(item =>
{
//正则表达式判断是否是数字，匹配的是多位数
if (Regex.IsMatch(item,"\\d+"))
{
//如果是数字直接入栈
stack.Push(item);
}
//如果是操作符
else
{
//出栈两个数字，并运算，再入栈
int num1 =int.Parse(stack.Pop()); int num2 = int.Parse(stack.Pop()); int result = ; if(item.Equals("+"))
{
result = num2 + num1;
}
else if(item.Equals("*"))
{
result = num2 * num1;
}
else if(item.Equals("/"))
{
result = num2 / num1;
}
else if (item.Equals("-"))
{
result = num2 - num1;
}
else
{
throw new Exception("无法识别符号");
} stack.Push(""+result);
}
}); //最后把stack中数据返回
return int.Parse(stack.Pop());
}
public class ReversePolandTransformation
{ public static void Test()
{
string expression = "1+((2+3)*4)-5"; //将字符串转换成List
List<string> infixExpression = ToInfixExpression(expression); string str = ""; infixExpression.ForEach(item =>
{
str = str + item + ",";
}); Console.WriteLine("中缀表达式对应的List:"+str); str = ""; //将中缀表达式转换成后缀表达式
List<string> suffixExpression = ParseSuffixExpression(infixExpression); suffixExpression.ForEach(item =>
{
str = str + item + ",";
}); Console.WriteLine("\n后缀表达式对应的List："+str); //结果计算
int result =PolandNotation.Calculate(suffixExpression); Console.WriteLine($"\n{expression}={result}");
}
}
最新文章
- RCP：如何移除Search对话框中不需要的项
- 计算机管理打不开的解决方法，直接cmd修改reg
- 面试体验：Google 篇（转）
- iOS开发 Xcode中的Info.plist字段含义
- .net I/O操作 导图
- 半个月学习的it内容
- MTV 和 MVC
- Java设计模式之动态代理
- Android为TV端助力 MediaPlayer的一些使用方法简历
- python变量类型&字符串的内建函数使用
- Tell Me About Yourself Example 1
- linux及安全第五周总结
- AGC027 D - Modulo Matrix 构造
- npm安装时一些错误
- formidable模块的使用
- [uboot]在uboot里面添加环境变量使用run来执行
- 20155319 2016-2017-2 《Java程序设计》第六周学习总结
- 一图看懂hadoop Yarn工作原理
- BZOJ2257 [Jsoi2009]瓶子和燃料 【裴蜀定理】
- 关于ListView的注意点