Cameudis's Homepage

Exp10re the W0r1d

0%

【Algorithm#0x01】数据结构-中缀表达式计算器

Posted on Edited on In , Views: Valine:

暑假写的中缀表达式和后缀表达式的转换程序只支持个位数加减法，实在是太菜了。
所以我参考教材上的方法（教材给的代码也只支持个位数加减法，实在是太菜了），把它升级了一下，写了一个 （中缀表达式）计算器。

首先是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();
    // void Test();

private:
    std::stack<double> numstk;  // store numbers to be calc
    std::stack<char> opstk;     // store opcodes waiting to be exec

    std::map<char, short> isp;  // in_stack_priority
    std::map<char, short> icp;  // in_coming_priority

    void Clear();               // clear numstk and opstk
    char ReadOperator();        // Read an operator from stdin, return '#' if encounter a new line
    bool AddOperator(char op);  // based on the priority, push op to opstk or call DoOperator
    void DoOperator(char op);   // Actually do the operation
};

其中，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
// Calculator.cpp
#include <string>
#include <cstdio>
#include <iostream>
#include <assert.h>
#include "Calculator.h"

using namespace std;

Calculator::Calculator()
{
    // set the piority of Operators
    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('#');

    // read and execute
    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()) == ' ') // jmp spaces
        ;

    if (op == '\n') {
        op = '#';
    }

    return op;
}

// return false if end
bool Calculator::AddOperator(char op)
{
    while (true) {
        // 操作符优先级 请参考Calculator()函数
        // 当前操作符优先级 高于 栈顶操作符优先级
        if (icp[op] > isp[opstk.top()]) {
            // 将其压栈
            opstk.push(op);
            break;
        }
        // 当前操作符优先级 等于 栈顶操作符优先级（只当括号配对或结束时发生）
        else if (icp[op] == isp[opstk.top()]) {
            // 若是括号匹配，那么将左括号弹出后继续
            if (opstk.top() == '(') {
                opstk.pop();
                break;
            }
            // 若是#和#匹配，则直接终止运行，返回false
            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;
        // double 类型不支持取模运算
        // 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才行……