zstu.4189: 逻辑运算(构建 && 前缀表达式入门）

4189: 逻辑运算

Time Limit: 1 Sec Memory Limit: 128 MB Submit: 274 Solved: 42

Description

还记得大学里学过的模电么，今天就让我们将与或非变成一道题吧。

给你一个与或非的表达式，求出这个表达式的值，表达式总共有八种字符。

三种逻辑运算符按照优先级排列如下。

‘！’：表示取反。

‘&’：逻辑与。

‘|’：逻辑或。

两个字符‘T’，‘F‘分别表示true和 false。

另外还有左右括号，空格三种字符。跟一般的表达式一样，括号可以改变优先级。

Input

每组数据输入一行字符串,字符串长度小于等于100.

Output

输出一个数0或1，表示逻辑表达式的答案。

Sample Input

Sample Output

HINT

Source

Wuyiqi

 1 #include<cstdio>
 2 #include<cstring>
 3 const int M = 3010 ;
 4 char s[M] ;
 5 
 6 struct Exp
 7 {
 8     char op[M] ;
 9     int num[M] ;
10     int top , tot ;
11     void init ()
12     {
13         top = 0 ;
14         tot = 0 ;
15         memset (op , 0 , sizeof(op) );
16         memset (num , 0 , sizeof(num) ) ;
17         op[0] = '(' ;
18     }
19     int calc (char k , int a , int b)
20     {
21         if (k == '&') {
22             return a && b ;
23         }
24         else if (k == '|') {
25             return a || b ;
26         }
27     }
28     bool prior (char a , char b)
29     {
30         if (b == '|') {
31             return a != '(' ;
32         }
33         if (b == '&') {
34             return a == '!' || a == '&' ;
35         }
36         return false ;
37     }
38     void solve ()
39     {
40         int len = strlen (s) ;
41         s[len ++] = ')' ;
42         for (int i = 0 ; i < len ; i++) {
43             if (s[i] == ' ') {
44                 continue ;
45             }
46             else if (s[i] == '(') {
47                 op[++ top] = '(' ;
48             }
49             else if (s[i] == ')') {
50                 if (top > 0 && op[top] != '(') {
51                     if (op[top] == '!') {
52                         num[tot] = !num[tot] ;
53                         top -- ;
54                     }
55                     else {
56                         num[tot - 1] = calc (op[top] , num[tot - 1] , num[tot]) ;
57                         tot -- ;
58                         top -- ;
59                     }
60                 }
61                 top -- ;
62             }
63             else if (s[i] == 'T' || s[i] == 'F') {
64                 num[++tot] = s[i] == 'T' ? 1 : 0 ;
65             }
66             else {
67                 while (top > 0 && prior (op[top] , s[i]) ) {
68                     if (op[top] == '!') {
69                         num[tot] = !num[tot] ;
70                         top -- ;
71                     }
72                     else {
73                         num[tot - 1] = calc (op[top] , num[tot - 1] , num[tot]) ;
74                         tot -- ;
75                         top -- ;
76                     }
77                 }
78                 op[++top] = s[i] ;
79             }
80         }
81         printf ("%d
" , num[1]) ;
82     }
83 };
84 Exp  E ;
85 
86 int main ()
87 {
88    // freopen ("a.txt" , "r" , stdin ) ;
89     while (gets (s) != NULL ) {
90         E.init () ;
91         E.solve () ;
92     }
93     return 0 ;
94 }

View Code

前缀表达式心得：
首先将文本串分成：数字串和文本串分析。

整个过程就是不断出队和入队的过程，大体上来说优先级高的字符将先实现 “计算” ， “计算”后该字符出队，而同时num[]里只会留下一个数字来表示此次运算的结果，而其他数字“出队” 。而“计算”的先后由 “字符的prior” && "()" 决定。

orz