逆波兰表达式

有一个自定义类型Query类，它可以实现搜索指定字符串的对应行并输出，同时支持&，|和~运算，于是我想通过用户输入字符串从而实现组合运算（包含括号），这时想起了逆波兰表达式

首先明确用户输入的是中缀表示式，但是中缀表达式是适用于人思考运算的，因为需要顾前顾后，但是计算机难以解读（因为一般是从左向右解析字符串的），并且需要考虑括号，而逆波兰表达式可以没有括号并且考虑了运算符优先级

一个简单的栗子：$1+(2+3) \times 5$=>$1 2 3 + 5 \times +$

逆波兰表达式如何运算：从左到右依次压栈，遇到运算符，取出栈顶两个操作数进行运算再放回去 ，最后输出栈顶

中缀转后缀

转化规则如下：

  • （：push
  • ）：）不push，pop栈顶直到遇到（或栈空
  • 运算符：pop优先级>=当前运算符的元素直到遇到（或栈空
  • 运算元：不push直接输出
  • 空格：直接跳过
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
std::map<char,unsigned char> priority_=
{
    {'|',0},{'&',0},
    {'~',1},
    {'(',2},{')',2}
};

bool is_Queryoperators(char op)
{
    if(op=='&' || op=='|' || op=='~') return true;
    else return false;
}

bool is_Queryoperands(char op)
{
    if(op!=' ' && op!='(' && op!=')' && !is_Queryoperators(op)) return true;
    else return false;
}

bool is_unary(char op)
{
    if(op=='~') return true;
    else return false;
}

bool is_binary(char op)
{
	if(op=='&' || op=='|') return true;
    else return false;
}

std::string get_reverse_polish_expr(std::string const& str)
{
    auto len=str.length();
    stack<char> operators;
    std::string res;
    for(std::size_t i=0;i!=len;++i)
    {
        auto c=str[i];
        if(c=='(')
        {
            operators.push(c);
        }else if(c==')'){
            while(!operators.empty() && operators.top()!='(')
            {
                res+=operators.top();operators.pop();res+=" ";
            }
            operators.pop();
        }else if(c==' '){
            continue;
        }else if(is_Queryoperators(c)){
            while(!operators.empty() && operators.top()!='(' && priority_[operators.top()] >= priority_[c])
            {
                res+=operators.top();operators.pop();res+=" ";
            }
            operators.push(c);
        }else if(is_Queryoperands(c)){
            res+=c;
            while(i+1<len)
            {
                auto next=str[i+1];
                if(is_Queryoperands(next)) 
                {
                    res+=next;++i;
                }
                else 
                {
                    res+=" ";break;
                }
            }
            if(i+1 == len) res+=" ";
        }
    }
    
    while(!operators.empty())
    {
       	res+=operators.top();operators.pop();res+=" ";
    }
    
    return res;
}

计算后缀表达式

先将得到的后缀表达式按” “分割成字符串向量，然后逐一push按上述方法计算即可

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
typedef std::vector<std::string> StringVector;

StringVector split(std::string str)
{
    StringVector contents;
    std::string::size_type loc=str.find(" ");
    while(loc != std::string::npos)
    {
        contents.emplace_back(str.substr(0,loc));
        str=str.substr(loc+1);
        loc=str.find(" ");
    }
    if(!str.empty()) contents.emplace_back(str);
    
    return contents;
}

Query eval(std::string expr)
{
    auto ops=split(get_reverse_polish_expr(expr));
    stack<Query> calc;
    for(auto& op : ops)
    {
        auto op_=op[0];
        if(is_unary(op_))
        {
            auto tmp=calc.top();calc.pop();
            calc.push(~tmp);
        }else if(is_binary(op_))
        {
            auto rhs=calc.top();calc.pop();
            auto lhs=calc.top();calc.pop();
            switch(op_)
            {
                case '&':calc.push(lhs & rhs);break;
                case '|':calc.push(lhs | rhs);break;
            }
        }else
        {
            calc.push(Query(op));
        }
    }
    
    return calc.top();
}