暑假写的中缀表达式和后缀表达式的转换程序只支持个位数加减法,实在是太菜了。 所以我参考教材上的方法(教材给的代码也只支持个位数加减法,实在是太菜了),把它升级了一下,写了一个 (中缀表达式)计算器 。
首先是Calculator类定义:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Calculator {public : Calculator (); double Run () ; private : std::stack<double > numstk; std::stack<char > opstk; std::map<char , short > isp; std::map<char , short > icp; void Clear () ; char ReadOperator () ; bool AddOperator (char op) ; void DoOperator (char op) ; };
其中,Run()是最顶层的函数,干的事情可以概括为:从stdin读入一行表达式并进行运算 。 具体来说,会依次调用Clear()来初始化两个栈,循环读入数字和操作符、然后用AddOperator()来处理操作符。如果AddOperator返回0,说明该操作符为标识结束的’#’,然后结束循环并输出、返回结果。
其实这次升级的关键之处不在于升级了读取表达式的方法,而主要在于操作符优先级的设置 。 Calculator类用两个map来存储操作符的优先级:
isp - in_stack_priority: 操作符在栈内的优先级
icp - in_coming_priority: 操作符在栈外的优先级
操作符
#
(
*, /
+, -
)
isp
0
1
5
3
6
icp
0
6
4
2
1
用这两个map巧妙地统一了优先级的比较,大大降低了AddOperator函数的代码复杂度。 我真的不知道这玩意是怎么被想出来的,实在是太简洁了……
下面是Calculator.cpp的代码:
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 #include <string> #include <cstdio> #include <iostream> #include <assert.h> #include "Calculator.h" using namespace std;Calculator::Calculator () { isp['#' ] = 0 ; icp['#' ] = 0 ; isp['(' ] = 1 ; icp['(' ] = 6 ; isp['*' ] = 5 ; icp['*' ] = 4 ; isp['/' ] = 5 ; icp['/' ] = 4 ; isp['%' ] = 5 ; icp['%' ] = 4 ; isp['+' ] = 3 ; icp['+' ] = 2 ; isp['-' ] = 3 ; icp['-' ] = 2 ; isp[')' ] = 6 ; icp[')' ] = 1 ; } double Calculator::Run () { Clear (); opstk.push ('#' ); while (true ) { double num = 0.0 ; if (scanf ("%lf" , &num)) { numstk.push (num); } char op = ReadOperator (); if (!AddOperator (op)) break ; } cout << numstk.top () << endl; return numstk.top (); } void Calculator::Clear () { while (!numstk.empty ()) { numstk.pop (); } while (!opstk.empty ()) { opstk.pop (); } } char Calculator::ReadOperator () { char op; while ((op = getchar ()) == ' ' ) ; if (op == '\n' ) { op = '#' ; } return op; } bool Calculator::AddOperator (char op) { while (true ) { if (icp[op] > isp[opstk.top ()]) { opstk.push (op); break ; } else if (icp[op] == isp[opstk.top ()]) { if (opstk.top () == '(' ) { opstk.pop (); break ; } else { return false ; } } else { DoOperator (opstk.top ()); opstk.pop (); } } return true ; } void Calculator::DoOperator (char op) { double a, b; b = numstk.top (); numstk.pop (); a = numstk.top (); numstk.pop (); switch (op) { case '+' : numstk.push (a+b); break ; case '-' : numstk.push (a-b); break ; case '*' : numstk.push (a*b); break ; case '/' : assert (b != 0.0 ); numstk.push (a/b); break ; default : cout << "INVALID OP: " << op; } }
使用起来也很简单,如下所示即可:
1 2 3 4 5 6 7 8 #include "Calculator.h" int main () { Calculator Cal; Cal.Run (); return 0 ; }
P.S. 我每次写程序几乎都会遇到一个需要de很久的bug。 这次是scanf(“%f”, &double_var); 无法正常读取数据至double类型,需要用%lf才行……