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

T

Sample Output

1

HINT

 

Source

1 #include
       
         2 #include
        
          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\n" , 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 }
        
       

前缀表达式心得：

首先将文本串分成 ： 数字串 和 文本串 分析。

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

orz