数据结构学习笔记-栈的应用

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//括号匹配 通过栈来实现
//将所有的左括号 压入栈 然如果碰到右括号 则令左括号弹出 
...
//为节省篇幅 省略定义栈结构相关代码

char pop(Stack* ps){ //出栈 并且返回出栈的节点的数据 这里的数据域是char类型
   if(ps->size == 0){
       printf("Empty stack!");
     return ;
 }else{
     ps->size -- ;
      char ret = ps->top->data;
      Node* temp = ps->top ;
     ps->top = ps->top->next;
     free(temp);
     temp = NULL ;
        return ret ;
 }
}

int isEmpty(Stack* ps){ // 判断栈是否为空栈
 return ps->size > 0 ? 0 : 1;
}

int checkPro(Stack* stack,char * s ){ //检测括号匹配
  int i ;
  char c ;
 for( i = 0 ; i <strlen(s); i++){
       if(s[i] == '('){
            push(stack,'s'); // 小括号 对应的数据为 's' 入栈
      }else if (s[i] == '['){
           push(stack,'m');// 中括号 对应的数据为 'm' 入栈
       }else if(s[i] == '{'){
           push(stack,'l');// 大括号
     }else if(s[i] == ')' && !isEmpty(stack)){ //碰到右小括号 且 栈不为空
          c = pop(stack); // 栈顶出栈
            if( c != 's'){ // 弹出的栈 不匹配
             return 0;
            }
        }else if(s[i] == ']' && !isEmpty(stack)){//同小括号
            c = pop(stack);
         if( c != 'm'){
              return 0;
            }
        }else if(s[i] == '}' && !isEmpty(stack)){//同小括号
           c = pop(stack);
         if( c != 'l'){
              return 0;
            }
        }
    }
    return isEmpty(stack); // 如果扫描进行结束没有退出 栈为空则匹配 非空则说明有多余的左括号
}

int main(){
    Stack stack ;
   init(&stack);
   char s[100];
 scanf("%s",&s);
 if(checkPro(&stack,s)){
       printf("yes");
  }else{
     printf("No");
   } 
   return 0;
}

#include<cstdio>  
#define MAX 150

bool val[MAX]; // 值栈 
int op[MAX];  //操作数栈 
int vp, pp; // 栈顶下标

/* 定义优先级  
    (:  0  
    | : 1 
   & : 2
    ! : 3
    ) : 4
*/   

void insert(bool b){  //入栈操作 
    while( pp &&  (op[pp-1] == 3) ){ // 处理!操作 如果操作数栈优先级为3 则说明为!操作 
     b = ! b; // 取反
       --pp; // 栈顶下标-1 相当于 弹出栈顶操作数
  }
    val[vp++] = b; // 将值压入栈中 并且vp++ 栈顶下标+1 
}

void calc(){ // 计算操作
  bool b = val[--vp]; // 取出一个值 
   bool a = val[--vp];
  int opr = op[--pp]; //取出一个操作数  这里的pp 和 vp 原来都是比实际栈顶下标大 1的
   insert(opr == 1 ? a | b : a & b ); // 压入结果  如果操作数为1即为 | 不为1 则为 &
}

int main(){
   int cnt = 0; // 计算第几个表达式的值
  char c ;
 while( ~(c = getchar()) ){ // 这是个小技巧 EOF = -1 按位取反 等价于 (c = getchar()) != EOF
      vp = pp = 0 ; // 初始化下标为 0 pp也代表着操作数的数量
       
      do{
         if( c == '('){ //左括号 压入栈中 
             op[pp++] = 0 ;
            }else if( c == ')'){
              while(pp && op[pp-1]){ //处理左括号以前所有的操作 处理完之后相当于消去了()
                    calc();
               }
                --pp; // pp-- 相当于弹出 ) 
               insert(val[--vp]); // 如果表达式为 !() 形式 还要计算一次! 
         }else if( c == '!'){
              op[pp++] = 3; //操作数 ! 入栈  
           }else if( c == '|'){ 
             while( pp && op[pp-1] >= 1){  // 计算|之前 优先级比|高的操作
                    calc();
               }
                op[pp++] = 1; // 压入 | 操作
         }else if( c == '&'){
              while( pp && op[pp-1] >= 2){ // 计算&之前 优先级比&高的操作
                 calc();
               }
                op[pp++] = 2 ;// 压入 & 操作
         }else if( c == 'V' || c == 'F'){
              insert(c == 'V' ? true : false); //压入 true or false
            }
            // 空格被忽略
     }while((c = getchar())!= '\n' &&  ~c); // ~c 等价于 c != EOF
      
      while(pp){ // 如果还存在操作数 继续计算
            calc(); 
      }
        //输出结果
       printf("Expression %d: %c\n",++cnt,(val[0] ? 'V' : 'F'));
   }
    return 0;
}