今天看书看到了逆波兰算法, 想想以后可能会用到类似的算法功能, 就写个 demo
逆波兰表达式又叫做, 我们常见的都是中缀表达式例如: 2+10*(3-1)
权重
我们根据运算符优先级去进栈出栈生成后缀表达式
此处用的字典存储的运算符权重
- public static Dictionary < string,
- int > dic = new Dictionary < string,
- int > () {
- {
- "+",
- 1
- },
- {
- "-",
- 1
- },
- {
- "*",
- 2
- },
- {
- "/",
- 2
- }
- }; // 权重
生成后缀表达式
把输入的公式拆解循环
遇到优先级较高的括号 "()" 此处办法是新添加一个内存去推算括号内的表达式 (遇到中括号情况类似可以使用)
根据字符是无法分别元素是否是一个完整的数字所以此处取巧添加了一个 bool 类型状态去管理元素 (数字元素结束添加空格分别元素)
- // 逆波兰公式 (推算后缀表达式)
- static string ClearUp(string str) {
- List < string > list = new List < string > ();
- List < string > list_tmp = new List < string > ();
- StringBuilder sb = new StringBuilder();
- StringBuilder sb_tmp = new StringBuilder();
- bool status = true; // 状态标示 (在元素前添加空格标示完整元素)
- foreach(char item in str) {
- switch (item) {
- case '+':
- status = false;
- Fun_Formula(item, list, sb, status);
- break;
- case '-':
- status = false;
- Fun_Formula(item, list, sb, status);
- break;
- case '*':
- status = false;
- Fun_Formula(item, list, sb, status);
- break;
- case '/':
- status = false;
- Fun_Formula(item, list, sb, status);
- break;
- case '(':
- // 使用临时栈保存原有数据 (开辟新栈计算片段)
- status = false;
- for (int i = 0; i < list.Count; i++) {
- list_tmp.Add(list[i]);
- }
- list.Clear();
- sb_tmp.Append(sb.ToString());
- sb.Clear();
- break;
- case ')':
- // 结束新内存 (赋值给主栈)
- status = false;
- for (int i = list.Count - 1; i >= 0; i--) {
- sb.Append(" " + list[i]);
- list.RemoveAt(i);
- }
- list = list_tmp;
- sb_tmp.Append(sb.ToString());
- sb = sb_tmp;
- break;
- default:
- status = true;
- sb.Append(item);
- break;
- }
- }
- for (int i = list.Count - 1; i >= 0; i--) // 计算结束栈内元素依次出栈
- {
- sb.Append(" " + list[i]);
- }
- return sb.ToString();
- }
- static void Fun_Formula(char item, List < string > list, StringBuilder sb, bool status) {
- if (list.Count == 0) {
- list.Add(item.ToString());
- }
- else {
- if (dic[item.ToString()] < dic[list[list.Count - 1].ToString()]) // 权重小于栈顶运算符全部出栈并新运算符进栈
- {
- for (int i = list.Count - 1; i >= 0; i--) {
- sb.Append(" " + list[i]);
- list.RemoveAt(i);
- }
- list.Add(item.ToString());
- }
- else if (dic[item.ToString()] == dic[list[list.Count - 1].ToString()]) // 权重一致进栈
- {
- list.Add(item.ToString());
- }
- else {
- list.Add(item.ToString()); // 权重大于栈顶元素进栈
- }
- }
- if (!status) {
- sb.Append(" ");
- }
- }
计算后缀表达式
循环出栈计算运算符之前的 2 个元素, 计算完成值进栈参与下次进栈
- // 根据后缀表达式计算 (以空格区分元素)
- static string Calculate(string str) {
- List < string > list = new List < string > ();
- double result;
- foreach(string item in str.Split(' ')) {
- switch (item) {
- case "+":
- result = double.Parse(list[list.Count - 2]) + double.Parse(list[list.Count - 1]);
- list.RemoveAt(list.Count - 1);
- list.RemoveAt(list.Count - 1);
- list.Add(result.ToString());
- break;
- case "-":
- result = double.Parse(list[list.Count - 2]) - double.Parse(list[list.Count - 1]);
- list.RemoveAt(list.Count - 1);
- list.RemoveAt(list.Count - 1);
- list.Add(result.ToString());
- break;
- case "*":
- result = double.Parse(list[list.Count - 2]) * double.Parse(list[list.Count - 1]);
- list.RemoveAt(list.Count - 1);
- list.RemoveAt(list.Count - 1);
- list.Add(result.ToString());
- break;
- case "/":
- result = double.Parse(list[list.Count - 2]) / double.Parse(list[list.Count - 1]);
- list.RemoveAt(list.Count - 1);
- list.RemoveAt(list.Count - 1);
- list.Add(result.ToString());
- break;
- default:
- list.Add(item.ToString());
- break;
- }
- }
- return list[0].ToString();
- }
效果图
结束语
程序存在着一些不足, 操作比较复杂, 代码比较臃肿, 还有线程安全的问题这些都需要优化, 后续优化我再整理下
请多多指教!
来源: http://www.cnblogs.com/hu772188392-163/p/5775367.html