布尔表达式

题意

完整题面见同目录的 problem.md。

思路

解析

这个题目的难度比较高,本质是考: 如果对中缀表达式进行计算

根据编译原理所学的知识,按下面的步骤来做

字符串转化成token流
token流根据运算符号的优先级转化成表达式树(核心)
对表达式树进行遍历,就可以得到前缀表达式,或,后缀表达式

难点就在于,转化成表达式树,很难操作,需要掌握

指针
树相关知识
递归

比较简单的方式,是把中缀表达式转成后缀表达式,

难点在于理解,

具体操作方式如下,

利用辅助栈

从左到右遍历中缀表达式的每个操作数和操作符。当读到操作数时，立即把它输出，即成为后缀表达式的一部分；若读到操作符，判断该符号与栈顶符号的优先级，若该符号优先级高于栈顶元素，则将该操作符入栈，否则就一次把栈中运算符弹出并加到后缀表达式尾端，直到遇到优先级低于该操作符的栈元素，然后把该操作符压入栈中。如果遇到”(”，直接压入栈中，如果遇到一个”)”，那么就将栈元素弹出并加到后缀表达式尾端，但左右括号并不输出。最后，如果读到中缀表达式的尾端，将栈元素依次完全弹出并加到后缀表达式尾端。

查看这里前缀、中缀、后缀表达式转换详解-CSDN博客

如何读取一行字符串
使用c风格的getline函数, getline, getwline, getdelim, getwdelim - cppreference.com
使用c++风格的std::getline stdgetline - cppreference.com
使用c++,cin.getline stdbasic_istreamCharT,Traitsgetline - cppreference.com

参考

代码

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int maxn = 1e5;

char str[maxn];
char a[maxn];
int idx;

template<typename T = int,int siz = maxn>
struct mystack{
    T sta[maxn];
    int head = 0;

    void clear() { head = 0;}

    void push(T a) { sta[head++] = a;}

    void pop(){head--;}

    T top() { return sta[head-1];}

    bool empty() { return head == 0;}
};

mystack<char> sta_opt;
mystack<bool> sta_num;

char prio[] = {'(',')','|','&','!','('};
int prio_len = sizeof(prio) /sizeof(prio[0]);

int priority_num(char a) {
    for(int i = 0 ; i< prio_len ;i++)
    {
        if( prio[i] == a)
            return i;
    }
    return -1;
}

//判断 a是否比c 优先级高
bool priority(char a,char c) {
    // 因为这个时候 操作数还没有出现
    // 
    if( a == '!' && c == '!') // 这个比较特别
        return false;
    return priority_num(a) >= priority_num(c);
}

//过滤空格,存到a里
void filter_space() {

    int len = strlen(str);
    idx = 0;
    for(int i = 0 ;i< len;i++)
    {
        if( str[i] == ' ') continue;
        a[++idx] = str[i];
    }
}

//计算数字
void calc() {

    //从sta_opt取一个运算符号
    char c = sta_opt.top();
    sta_opt.pop();
    bool b = sta_num.top();
    sta_num.pop();
    if( c == '|') {
        bool a = sta_num.top();
        sta_num.pop();
        sta_num.push(a || b);
        // cout <<  a << c << b << endl;
    }
    else if( c == '&')
    {
        bool a = sta_num.top();
        sta_num.pop();
        sta_num.push(a && b);
        // cout <<  a << c << b << endl;
    }
    else if( c == '!') {
        sta_num.push(!b);
        // cout <<   c << b << endl;;
    }
 
}

void work() {
    sta_opt.clear();
    sta_num.clear();
    for(int i =1;i<=idx;i++) {
        char c = a[i];
        if( c == 'F' || c == 'V') {
            sta_num.push( c == 'V');
            continue;
        }

        //运行到这里表示是运算符号

        // ( 必须直接入栈
        // 可以认为 ( 是一个有限级很低的运算符号,
        // 但是它不能让栈里的操作符元素弹出
        // 因为( 可以认为不能和其它操作符 ! & | 发生比较
        if( c == '(')
        {
            sta_opt.push('(');
            continue;
        }

        // 没有比栈顶的优先级高
        while( !sta_opt.empty() && priority(sta_opt.top(),c))
        {
            calc();
        }

        sta_opt.push(c);
        if( c == ')') {
            sta_opt.pop();
            sta_opt.pop();
        }

    }

    while( !sta_opt.empty() )
        calc();

}

int main() {
    
    while( cin.getline(str,maxn)) {
        // cout << str << endl;
        filter_space();
        work();
        if( sta_num.top() )
            cout << "V" << endl;
        else
            cout << "F" << endl;
    }

    return 0;
}

目录

题意

思路

解析

参考

代码

复杂度

总结