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

T

Sample Output

1

HINT

 

Source

*qi

 #include<cstdio>
 #include<cstring>
 const int M =  ;
 char s[M] ;

 struct Exp
 {
     char op[M] ;
     int num[M] ;
     int top , tot ;
     void init ()
     {
         top =  ;
         tot =  ;
         memset (op ,  , sizeof(op) );
         memset (num ,  , sizeof(num) ) ;
         op[] = '(' ;
     }
     int calc (char k , int a , int b)
     {
         if (k == '&') {
             return a && b ;
         }
         else if (k == '|') {
             return a || b ;
         }
     }
     bool prior (char a , char b)
     {
         if (b == '|') {
             return a != '(' ;
         }
         if (b == '&') {
             return a == '!' || a == '&' ;
         }
         return false ;
     }
     void solve ()
     {
         int len = strlen (s) ;
         s[len ++] = ')' ;
         for (int i =  ; i < len ; i++) {
             if (s[i] == ' ') {
                 continue ;
             }
             else if (s[i] == '(') {
                 op[++ top] = '(' ;
             }
             else if (s[i] == ')') {
                 if (top >  && op[top] != '(') {
                     if (op[top] == '!') {
                         num[tot] = !num[tot] ;
                         top -- ;
                     }
                     else {
                         num[tot - ] = calc (op[top] , num[tot - ] , num[tot]) ;
                         tot -- ;
                         top -- ;
                     }
                 }
                 top -- ;
             }
             else if (s[i] == 'T' || s[i] == 'F') {
                 num[++tot] = s[i] == 'T' ?  :  ;
             }
             else {
                 while (top >  && prior (op[top] , s[i]) ) {
                     if (op[top] == '!') {
                         num[tot] = !num[tot] ;
                         top -- ;
                     }
                     else {
                         num[tot - ] = calc (op[top] , num[tot - ] , num[tot]) ;
                         tot -- ;
                         top -- ;
                     }
                 }
                 op[++top] = s[i] ;
             }
         }
         printf ("%d\n" , num[]) ;
     }
 };
 Exp  E ;

 int main ()
 {
    // freopen ("a.txt" , "r" , stdin ) ;
     while (gets (s) != NULL ) {
         E.init () ;
         E.solve () ;
     }
     return  ;
 }

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

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

orz