中缀表达式转化前后缀引发的思考

发表于 | 分类于 ，
字数统计: 2,756 字

纠结星人的胜利。

平凡栈实现

一谈起中缀表达式转前后缀表达式，网上的解决办法中，有一大半是用栈实现，我称之为平凡实现。因为这种方法总让我感觉是在头痛医头、脚痛医脚，拓展性不大。下面来看看。

中缀表达式转后缀表达式

原理

请原谅我很难把道理讲透，只能说说做法。大体上来看就是让操作符入栈，通过比较读取到的操作符和栈顶操作符优先级，进行入栈和出栈。

  1. 遇到操作数直接输出
  2. 遇到左括号，左括号入栈
  3. 遇到右括号，将pop到左括号为止
  4. 遇到操作符，把小于等于它优先级的操作符都出栈，直到左括号或者栈空，最后让它入栈
  5. 读取完表达式，将栈全部pop

示例

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
1 - ( 3 * 2 - 5 ) * 4
^
output: 1        
stack:
1 - ( 3 * 2 - 5 ) * 4     
  ^
output: 1       
stack: -
1 - ( 3 * 2 - 5 ) * 4
    ^     
// 左括号入栈
output: 1
stack: - (
1 - ( 3 * 2 - 5 ) * 4
      ^
output: 1 3      
stack: - (
1 - ( 3 * 2 - 5 ) * 4
        ^
output: 1 3      
stack: - ( *
1 - ( 3 * 2 - 5 ) * 4
          ^
output: 1 3 2  
stack: - ( *
1 - ( 3 * 2 - 5 ) * 4
            ^
// 栈顶是*，-优先级比它小，*输出，-入栈
output: 1 3 2 *     
stack: - ( -
1 - ( 3 * 2 - 5 ) * 4
              ^
output: 1 3 2 * 5     
stack: - ( -
1 - ( 3 * 2 - 5 ) * 4
                ^
// 遇到右括号，pop到左括号
output: 1 3 2 * 5 -    
stack: -
1 - ( 3 * 2 - 5 ) * 4
                  ^
output: 1 3 2 * 5 - 
stack: - *
1 - ( 3 * 2 - 5 ) * 4
                    ^
output: 1 3 2 * 5 - 4
stack: - *
// 最后全部pop
output: 1 3 2 * 5 - 4 * -
stack:

主要代码

数据结构：

1
2
3
4
5
6
7
8
9
10
enum OP_TYPE { OP_NUM, OP_SYMBOL, OP_ADD, OP_SUB, OP_MUL, OP_DIV, OP_LBAC, OP_RBAC, };
struct Token
{
    OP_TYPE _type;
    int _value;
    Token(int v) : _type(OP_NUM), _value(v) {}
    Token(char c) : _type(OP_SYMBOL), _value(CharToOp(c)) {}
};

实现代码：

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
void NiToPost(const std::vector<Token> &nifix, std::vector<Token> &post)
{
    std::stack<Token> stk;
    for (const auto &i : nifix)
    {
        if (i._type == OP_NUM)
        {
            post.push_back(i);
        }   // 操作数直接输出
        else
        {
            auto iv = i._value;
            if (iv == OP_LBAC)
            {
                stk.push(i);
            }   // 左括号直接入栈
            else if (iv == OP_RBAC)
            {
                while (stk.top()._value != OP_LBAC)
                {
                    post.push_back(stk.top());
                    stk.pop();
                }
                stk.pop();
            }   // 右括号，pop到左括号
            else
            {
                while (!stk.empty() && stk.top()._value != OP_LBAC && CalcPriority(i) <= CalcPriority(stk.top()))
                {
                    post.push_back(stk.top());
                    stk.pop();
                }
                stk.push(i);
            }   // 遇到操作符，把小于等于它优先级的操作符都出栈，直到左括号或者栈空，最后让它入栈
        }
    }
    while (!stk.empty())
    {
        post.push_back(stk.top());
        stk.pop();
    }   // 读取完表达式，将栈全部pop
}

中缀表达式转前缀表达式

原理

和转后缀很接近，但是稍麻烦些，需要从后往前读取，最后再翻转过来。而且优先级的比较和转后缀也有所不同，转后缀是小于等于，这里是小于。

  1. 从后向前读取表达式
  2. 遇到操作数直接输出
  3. 遇到右括号，右括号入栈
  4. 遇到左括号，将pop到右括号为止
  5. 遇到操作符，把小于它优先级的操作符都出栈，直到右括号或者栈空，最后让它入栈
  6. 读取完表达式，将栈全部pop
  7. 逆序输出

主要代码

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
void NiToPre(const std::vector<Token> &nifix, std::vector<Token> &pre)
{
    std::stack<Token> stk;
    for (auto it = nifix.rbegin(); it != nifix.rend(); ++it)
    // 从后往前读取
    {
        auto i = *it;
        if (i._type == OP_NUM)
        {
            pre.push_back(i);
        }   // 操作数直接输出
        else
        {
            auto iv = i._value;
            if (iv == OP_RBAC)
            {
                stk.push(i);
            }   // 右括号直接入栈
            else if (iv == OP_LBAC)
            {
                while (stk.top()._value != OP_RBAC)
                {
                    pre.push_back(stk.top());
                    stk.pop();
                }
                stk.pop();
            }   // 左括号，pop到右括号
            else
            {
                while (!stk.empty() && stk.top()._value != OP_RBAC && CalcPriority(i) < CalcPriority(stk.top()))
                {
                    pre.push_back(stk.top());
                    stk.pop();
                }
                stk.push(i);
            }   // 遇到操作符，把小于它优先级的操作符都出栈，直到左括号或者栈空，最后让它入栈
        }
    }
    while (!stk.empty())
    {
        pre.push_back(stk.top());
        stk.pop();
    }   // 读取完表达式，将栈全部pop
    reverse(pre.begin(), pre.end());    // 最后逆序输出
}

结果

0

平凡二叉树实现

如果构造一棵语法树，那就想输出什么缀就输出什么缀，无非就是前序遍历和后序遍历。
像这样：

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
void PreTrav(Node *&Node)
{
    if (Node->left == nullptr)
    {
        std::cout << Node->token._value << ' ';
    }
    else
    {
        std::cout << OpToChar(Node->token._value) << ' ';
        PreTrav(Node->left);
        PreTrav(Node->right);
    }
}
void PostTrav(Node *&Node)
{
    if (Node->left == nullptr)
    {
        std::cout << Node->token._value << ' ';
    }
    else
    {
        PostTrav(Node->left);
        PostTrav(Node->right);
        std::cout << OpToChar(Node->token._value) << ' ';
    }
}

终端输出：

1
2
后序遍历：7 6 - 5 4 3 / + + 2 1 * -
前序遍历：- + - 7 6 + 5 / 4 3 * 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
void output_impl(Node *n, bool left, std::string const &indent)
{
    if (n->right)
    {
        output_impl(n->right, false, indent + (left ? "|     " : "      "));
    }
    std::cout << indent;
    std::cout << (left ? '`' : '.');
    std::cout << "--- ";
    if (n->token._type == OP_NUM)
    {
        std::cout << n->token._value << std::endl;
    }
    else
    {
        std::cout << OpToChar(n->token._value) << std::endl;
    }
    if (n->left)
    {
        output_impl(n->left, true, indent + (left ? "      " : "|     "));
    }
}
void output(Node *root)
{
    if (root->right)
    {
        output_impl(root->right, false, "");
    }
    if (root->token._type == OP_NUM)
    {
        std::cout << root->token._value << std::endl;
    }
    else
    {
        std::cout << OpToChar(root->token._value) << std::endl;
    }
    if (root->left)
    {
        output_impl(root->left, true, "");
    }
}

终端输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
      .--- 1
.--- *
|     `--- 2
-
|                 .--- 3
|           .--- /
|           |     `--- 4
|     .--- +
|     |     `--- 5
`--- +
      |     .--- 6
      `--- -
            `--- 7

原理

为什么又叫作平凡实现呢，因为这种实现在构造二叉树的时候，本质上和栈实现没太大差别，还是根据优先级进行入栈出栈。

主要代码

数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Node
{
    Token token;
    Node *left = nullptr;
    Node *right = nullptr;
    Node(const Token &t) : token(t) {}
    Node(const Token &t, Node *l, Node *r) : token(t), left(l), right(r) {}
    ~Node()
    {
        delete left;
        delete right;
    }
};

实现代码：

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
void NiToBitree(const std::vector<Token> &nifix, Node *&Tree)
{
    std::stack<Node *> branch;
    std::stack<Token> op;
    for (const auto &i : nifix)
    {
        if (i._type == OP_NUM)
        {
            branch.push(new Node(i));
        }
        else
        {
            auto iv = i._value;
            if (iv == OP_LBAC)
            {
                op.push(i);
            }
            else if (iv == OP_RBAC)
            {
                while (op.top()._value != OP_LBAC)
                {
                    auto r = branch.top();
                    branch.pop();
                    auto l = branch.top();
                    branch.pop();
                    branch.push(new Node(op.top(), l, r));
                    op.pop();
                }
                op.pop();
            }
            else
            {
                while (!op.empty() && op.top()._value != OP_LBAC && CalcPriority(i) <= CalcPriority(op.top()))
                {
                    auto r = branch.top();
                    branch.pop();
                    auto l = branch.top();
                    branch.pop();
                    branch.push(new Node(op.top(), l, r));
                    op.pop();
                }
                op.push(i);
            }
        }
    }
    while (!op.empty())
    {
        auto r = branch.top();
        branch.pop();
        auto l = branch.top();
        branch.pop();
        branch.push(new Node(op.top(), l, r));
        op.pop();
    }
    Tree = branch.top();
}

优雅实现之语法分析器

我实在是不满足平凡实现，觉得它太实在了，老老实实总会遭人欺负的。于是我对着这四则运算表达式圈圈画画，没想到还真看出来了端倪。然后赶紧上搜索引擎看看有没同道中人已经实现过这种思路，果然……轮子哥在八年前，也就是在我还是小学生的时候，就已经实现过了……好吧，下面一起来看看。

单位化

Exp

一个表达式，可以看成是若干个单位通过'+', '-'连接起来，比如：

1
2
3
4
1 + 2            // 单位：1, 2
3                // 单位：3
5 + (4 - 2) * 3  // 单位：5, (4 - 2) * 3
6 * 4 - 3        // 单位：6 * 4, 3

我们把这种单位抽象出来，取个名字：Factor。

因此，表达式可以这样来表示： Exp = Factor (( '+' | '-' ) Factor)*，十分的简洁明了。

Factor

接下来Factor也不难表示，可以看成是若干个单位通过'*', '/'连接起来，比如：

1
2
3
1 * 2       // 单位：1, 2
(4 - 2) * 3 // 单位：(4 - 2), 3
5 / 4 * 6   // 单位：5, 4, 6

我们把这种单位抽象出来，取个名字：Term。

因此，Factor可以这样来表示：Factor = Term (( '*' | '/' ) Term)*

Term

最后就是最基本的单位Term，通过观察可知Term要么是数字，要么是括号括起来的一个表达式：

1
2
50          --> Term
(4 - 2)     --> Term

因此Term可以这样来表示：Term = <数字> | '(' Exp ')'

我们可以通过上面的关系来构造语法树，可以想象，生成过程真的很像一棵树的生长。

没错！我就是想要这种非常函数式的实现，这种抽象美得让人陶醉。鲁迅先生好像说过：

Any problem in computer science can be solved with another level of indirection.
计算机科学里面，没有什么问题是多加一层抽象不可以解决的。

语法树特点

1
2
3
4
5
6
7
8
9
10
11
12
13
      .--- 1
.--- *
|     `--- 2
-
|                 .--- 3
|           .--- /
|           |     `--- 4
|     .--- +
|     |     `--- 5
`--- +
      |     .--- 6
      `--- -
            `--- 7

借用上边画出来的语法树，来观察语法树的结构：

  • 一个数字表达式的节点一定是一个叶子节点，没有左右孩子节点。
  • 一个二元运算表达式一定有两个孩子节点，因为二元运算符号左右两边必然都要有表达式。这两个叶子节点的类型，是抽象的表达式，既可以是二元运算表达式，也可以是数字表达式。

由此可以定义Expression作为基类，派生出NumberExpression类和BinaryExpression类，来表示数字表达式和二元运算表达式。
1

注：下面都是用现代C++来实现，区别于轮子哥八年前写的古老C++版。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Expression
{
  public:
    virtual ~Expression() = default;
};
class NumberExpression : public Expression
{
  public:
    int Value;
    NumberExpression(int number) : Value(number) {}
};
class BinaryExpression : public Expression
{
  public:
    std::shared_ptr<Expression> First;
    std::shared_ptr<Expression> Second;
    BinaryOperator Op;
    BinaryExpression(BinaryOperator theOp, std::shared_ptr<Expression> theLeft, std::shared_ptr<Expression> theRight) : Op(theOp), First(theLeft), Second(theRight) {}
};

BinaryOperator枚举类型也要现代一点：

1
2
3
4
5
6
7
enum class BinaryOperator
{
    Plus,
    Minus,
    Multiply,
    Divide,
};

构造语法树

辅助函数

Is

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool Is(const char *&Stream, const char *Text)
{
    size_t len = strlen(Text);
    /*保存参数*/
    const char *Read = Stream;
    /*过滤空格*/
    while (*Read == ' ')
        Read++;
    if (strncmp(Read, Text, len) == 0)
    {
        Stream = Read + len;
        return true;
    }
    else
    {
        return false;
    }
}

用于判断Stream是不是由Text开头，如果是就将Stream偏移strlen(Text)个字符。

GetNumber

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
std::shared_ptr<Expression> GetNumber(const char *&Stream)
{
    int Result = 0;
    bool GotNumber = false;
    const char *Read = Stream;
    while (*Read == ' ')
        Read++;
    while (true)
    {
        char c = *Read;
        if ('0' <= c && c <= '9')
        {
            Result = Result * 10 + (c - '0');
            GotNumber = true;
            Read++;
        }
        else
        {
            break;
        }
    }
    if (GotNumber)
    {
        Stream = Read;
        return std::make_shared<NumberExpression>(Result);
    }
    else
    {
        throw Exception(Stream, "此处需要表达式");
    }
}

这个函数的作用是，按照数字的方式，对Stream进行解析，如果解析成功，就将Stream指针的位置移动到解析完成的最后位置（代码中的Read），然后调用make_shared，构造一个shared_ptr并返回；而如果失败（即一个数字都没找到），则抛出一个异常。跟Is一样，这个函数会过滤掉开头的空格。

辅助异常类

1
2
3
4
5
6
7
8
9
10
struct Exception
{
    const char *Start;
    const char *Error;
    Exception(const char *aStart, const char *aError)
    {
        Start = aStart;
        Error = aError;
    }
};

核心代码

1
2
3
std::shared_ptr<Expression> GetTerm(const char *&Stream);
std::shared_ptr<Expression> GetFactor(const char *&Stream);
std::shared_ptr<Expression> GetExp(const char *&Stream);

三个解析函数，完成语法树的构造。

GetExp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
std::shared_ptr<Expression> GetExp(const char *&Stream)
{
    const char *Read = Stream;
    std::shared_ptr<Expression> Result = GetFactor(Read);
    while (true)
    {
        BinaryOperator Operator;
        if (Is(Read, "+"))
        {
            Operator = BinaryOperator::Plus;
        }
        else if (Is(Read, "-"))
        {
            Operator = BinaryOperator::Minus;
        }
        else
        {
            break;
        }
        Result = std::make_shared<BinaryExpression>(Operator, Result, GetFactor(Read));
    }
    Stream = Read;
    return Result;
}

完成：Exp = Factor (( '+' | '-' ) Factor)*
构造出来的形状是这样的：
1

GetFactor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
std::shared_ptr<Expression> GetFactor(const char *&Stream)
{
    const char *Read = Stream;
    std::shared_ptr<Expression> Result = GetTerm(Read);
    while (true)
    {
        BinaryOperator Operator;
        if (Is(Read, "*"))
        {
            Operator = BinaryOperator::Multiply;
        }
        else if (Is(Read, "/"))
        {
            Operator = BinaryOperator::Divide;
        }
        else
        {
            break;
        }
        Result = std::make_shared<BinaryExpression>(Operator, Result, GetTerm(Read));
    }
    Stream = Read;
    return Result;
}

完成：Factor = Term (( '*' | '/' ) Term)*

GetTerm

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
std::shared_ptr<Expression> GetTerm(const char *&Stream)
{
    try
    {
        return GetNumber(Stream);
    }
    catch (Exception &e)
    {
        const char *Read = Stream;
        if (Is(Read, "("))
        {
            auto Result = GetExp(Read);
            if (Is(Read, ")"))
            {
                Stream = Read;
                return Result;
            }
            else
            {
                throw Exception(Stream, "此处需要右括号");
            }
        }
        else
        {
            throw e;
        }
    }
}

完成：Term = <数字> | '(' Exp ')'

好了，这样就搞定啦！虽然代码看起来有点点长，可是思路是十分清晰自然的。我相信用函数式语言来写会短几十倍的，用C++写只是为了照顾大部分人。最后奉上测试代码。

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
    auto a = "75 + 66 * (555-333*444) - 332 * 111";
    try
    {
        auto exp = GetExp(a);
    }
    catch (Exception &e)
    {
        std::cout << e.Start << e.Error << std::endl;
    }
    //Do what you want to do
    return 0;
}

完整代码：https://gist.github.com/zhongzc/3f9cc3024684ab5b0b70729a348c5f6a