题目描述
ACMOJ - 1486 - 布尔表达式求值
给定合法的布尔表达式，规则如下：
- $\text{f}$：字面量 false
- $\text{t}$: 字面量 true
- $\text{!}(x)$：非运算 not
- $\text{&}(x_1,x_2,\dots )$：与运算 and
- $\text{|}(x_1,x_2,\dots )$：或运算 or
计算布尔表达式的结果，保证长度 $|S|\leq10^4$
问题分析
与后缀表达式的处理方式类似，我们采用栈来存储表达式内容，由于括号和逗号并不产生实际语义，我们只保存操作符和字面量
顺序遍历表达式，将操作符和字面量依次入栈，忽略左括号和逗号，每当遇到右括号时执行出栈并完成一组计算，具体细节如下：
- 不断弹出栈顶，直到遇到操作符
- 记录弹出字面量的类型，即是否出现过 true 和 false
- 对于 not 运算，只需取反唯一的运算数
- 对于 and 运算，若出现过 false，结果为 false，否则为 true
- 对于 or 运算，若出现过 true 结果为 true，否则为 false
最后，我们将本次计算所得的结果以字面量的形式放回栈顶
该算法可在 $O(n)$ 的时间复杂度内完成表达式的计算
代码
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
147
| #include <cstdio>
#include <cstring>
const int SIZE = 20005;
template <typename ElementType>
class Stack
{
public:
virtual ~Stack() {}
virtual bool empty() const = 0;
virtual void push(const ElementType &element) = 0;
virtual ElementType pop() = 0;
virtual ElementType top() const = 0;
virtual void clear() = 0;
};
template <typename ElementType>
class LinkedStack : public Stack<ElementType>
{
private:
struct StackNode
{
ElementType data;
StackNode *next;
StackNode() : next(nullptr) {}
StackNode(const ElementType &_data, StackNode *_next = nullptr) : data(_data), next(_next) {}
~StackNode() {}
};
StackNode *head;
public:
LinkedStack();
~LinkedStack();
bool empty() const;
void push(const ElementType &element);
ElementType pop();
ElementType top() const;
void clear();
};
template <typename ElementType>
LinkedStack<ElementType>::LinkedStack()
{
head = nullptr;
}
template <typename ElementType>
LinkedStack<ElementType>::~LinkedStack()
{
clear();
}
template <typename ElementType>
bool LinkedStack<ElementType>::empty() const
{
return head == nullptr;
}
template <typename ElementType>
void LinkedStack<ElementType>::push(const ElementType &element)
{
head = new StackNode(element, head);
}
template <typename ElementType>
ElementType LinkedStack<ElementType>::pop()
{
if (head == nullptr)
throw "Stack is already empty!";
StackNode *temp = head;
ElementType value = temp->data;
head = head->next;
delete temp;
return value;
}
template <typename ElementType>
ElementType LinkedStack<ElementType>::top() const
{
if (head == nullptr)
throw "Stack is already empty!";
return head->data;
}
template <typename ElementType>
void LinkedStack<ElementType>::clear()
{
StackNode *temp;
while (head != nullptr)
{
temp = head;
head = head->next;
delete temp;
}
}
LinkedStack<char> waiting;
char expression[SIZE];
int length, count = 0;
int main()
{
scanf("%s", expression);
length = strlen(expression);
for (int position = 0; position < length; position++)
{
if (expression[position] == '(' || expression[position] == ',')
continue;
else if (expression[position] == ')')
{
bool right = 0, wrong = 0;
while (!waiting.empty() && (waiting.top() == 't' || waiting.top() == 'f'))
{
if (waiting.pop() == 't')
right = 1;
else
wrong = 1;
}
char operation = waiting.pop();
if (operation == '!')
{
if (right)
waiting.push('f');
else
waiting.push('t');
}
else if (operation == '&')
{
if (wrong)
waiting.push('f');
else
waiting.push('t');
}
else if (operation == '|')
{
if (right)
waiting.push('t');
else
waiting.push('f');
}
}
else
waiting.push(expression[position]);
}
printf("%d\n", waiting.top() == 't' ? 1 : 0);
return 0;
}
|