数据结构(三)——栈和队列的应用

3.3 栈和队列的应用

3.3.1 栈在括号匹配中的应用

用栈实现括号匹配：

最后出现的左括号最先被匹配（栈的特性——LIFO）。
遇到左括号就入栈，遇到右括号，就“消耗”一个左括号（出栈）。

匹配失败情况：

扫描到右括号且栈空，则该右括号单身。
扫描完所有括号后，栈非空，则该左括号单身。
左右括号不匹配。

算法实现

// 判断长度为length的字符串str中的括号是否匹配
bool bracketCheck(char str[], int length){ 
    SqStack S;      
    InitStack(S);     //初始化一个栈
    // 遍历str    
    for(int i=0; i<length; i++){   //循环从左往右依次扫描字符
        if(str[i] == '(' || str[i] == '[' || str[i] == '{'){    
            Push(S, str[i]);                // 扫描到左括号，入栈     
        }else{              
            if(StackEmpty(S))                  // 扫描到右括号且当前栈空   
                return false;                  // 匹配失败
            char topElem;                      // 用topElem接收栈顶元素   
            Pop(S, topElem);                   // 栈顶元素出栈      
            if(str[i] == ')' && topElem != '(' )     //不匹配的情况直接匹配失败
                return false;           
            if(str[i] == ']' && topElem != '[' )  
                return false;   
            if(str[i] == '}' && topElem != '{' )   
                return false;              }   
    }  
    return StackEmpty(S);        // 扫描完毕若栈空则说明匹配成功    
}


#define MaxSize 10            //定义栈元素中的最大个数
typedef struct{    
    char data[MaxSize];       //静态数组存放栈中元素
    int top;                  //栈顶指针
}SqStack;

//初始化栈
void InitStack(SqStack &S);

//判断是否为空
bool StackEmpty(SqStack &S);

//新元素入栈
bool Push(SqStack &S, char x);

//栈顶元素出栈，用x返回
bool Pop(SqStack &S, char &x);

3.3.2_1 栈在表达式求值中的应用(上)

算数表达式
(15 ÷ (7 − (1 + 1))) × 3) − (2 + (1 + 1))
③ ② ① ④ ⑦ ⑥ ⑤
15 ÷ 7 − 1 + 1 × 3 − 2 + 1 + 1
① ② ④ ③ ⑤ ⑥ ⑦

由三个部分组成：操作数、运算符、界限符
界限符是必不可少的，反映了计算的先后顺序

上面这种常用的算术表达式就是中缀表达式
中缀表达式是一种通用的算术或逻辑公式表示方法，运算符以中缀形式处于操作数的中间。但对于计算机来说中缀表达式是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。

前缀表达式（波兰表达式）：前缀表达式的运算符位于两个操作数之前。

后缀表达式（逆波兰表达式）：后缀表达式的运算符位于两个操作数之后。

中缀转后缀的手算方法：
① 确定中缀表达式中各个运算符的运算顺序
② 选择下一个运算符，按照「左操作数右操作数运算符」的方式组合成一个新的操作数
③ 如果还有运算符没被处理，就继续 ②

为了保证手算和机算结果相同可以采用“左优先”原则：只要左边的运算符能先计算就优先算左边的

后缀表达式的手算方法：
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
注意：两个操作数的左右顺序

用栈实现后缀表达式的计算(机算)：
①从左往右扫描下一个元素，直到处理完所有元素
②若扫描到操作数则压入栈，并回到①；否则执行③
③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①

中缀转前缀的手算方法：
① 确定中缀表达式中各个运算符的运算顺序
② 选择下一个运算符，按照「运算符左操作数右操作数」的方式组合成一个新的操作数
③ 如果还有运算符没被处理，就继续 ②
右优先”原则：只要右边的运算符能先计算，就优先算右边的

用栈实现前缀表达式的计算：
①从右往左扫描下一个元素，直到处理完所有元素
②若扫描到操作数则压入栈，并回到①；否则执行③
③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①
注意：先出栈的是"左操作数"

3.3.2_2 栈在表达式求值中的应用(下)

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
从左到右处理各个元素，直到末尾。可能遇到三种情况：
① 遇到操作数。直接加入后缀表达式。
② 遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意：“(”不加入后缀表达式。
③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(” 或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式

#define MaxSize 40 
typedef struct{     
    char data[MaxSize];   
    int top;
}SqStack;

typedef struct{  
    char data[MaxSize];  
    int front,rear;
}SqQueue;

void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack &S, char x);
bool Pop(SqStack &S, char &x);
void InitQueue(SqQueue &Q);
bool EnQueue(LQueue &Q, char x);
bool DeQueue(LQueue &Q, char &x);
bool QueueEmpty(SqQueue Q);

// 判断元素ch是否入栈
int JudgeEnStack(SqStack &S, char ch){
    char tp = S.data[S->top];   
    // 如果ch是a~z则返回-1    
    if(ch >= 'a' && ch <= 'z')   
        return -1;    
    // 如果ch是+、-、*、/且栈顶元素优先级大于等于ch则返回0  
    else if(ch == '+' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))   
        return 0;     
    else if(ch == '-' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))   
        return 0;  
    else if(ch == '*' && (tp == '*' || tp == '/'))  
        return 0;    
    else if(ch == '/' && (tp == '*' || tp == '/'))     
        return 0;    
    // 如果ch是右括号则返回2   
    else if(ch == ')')      
        return 2;     
    // 其他情况ch入栈，返回1   
    else return 1;
}

// 中缀表达式转后缀表达式
int main(int argc, char const *argv[]) {  
    SqStack S;     
    SqQueue Q;	 
    InitStack(S); 
    InitQueue(Q);  
    char ch;	  
    printf("请输入表达式，以“#”结束：");  
    scanf("%c", &ch);   
    while (ch != '#'){  
        // 当栈为空时     
        if(StackEmpty(&S)){ 
            // 如果输入的是数即a~z，直接入队 
            if(ch >= 'a' && ch <= 'z')               
                EnQueue(Q, ch);      	
            // 如果输入的是运算符，直接入栈    
            else                      
                Puch(S, ch);       
        }else{                
            // 当栈非空时，判断ch是否需要入栈 
            int n = JudgeEnStack(S, ch);     
            // 当输入是数字时直接入队      	
            if(n == -1){        	    
                EnQueue(Q, ch);        
            }else if(n == 0){       
                // 当输入是运算符且运算符优先级不高于栈顶元素时    
                while (1){         
                    // 取栈顶元素入队    
                    char tp;        
                    Pop(S, tp);      
                    EnQueue(Q, tp);         
                    // 再次判断是否需要入栈     
                    n = JudgeEnStack(S, ch);
                    // 当栈头优先级低于输入运算符或者栈头为‘)’时，入栈并跳出循环  
                    if(n != 0){           
                        EnStack(S, ch);           
                        break;              
                    }                   
                }            
            }else if(n == 2){  
                // 当出现‘)’时 将()中间的运算符全部出栈入队   
                while(1){                
                    char tp;                
                    Pop(S, tp);             
                    if(tp == '(')          
                        break;        
                    else            
                        EnQueue(Q, tp);    
                }             
            }else{        
                // 当运算符优先级高于栈顶元素或出现‘(’时直接入栈     
                Push(S, ch);         
            }          
        }         
        scanf("%c", &ch);   
    }     
    // 将最后栈中剩余的运算符出栈入队 
    while (!StackEmpty(S)){	  
        char tp;            
        Pop(S, tp);      
        EnQueue(Q, tp);  
    }      
    // 输出队中元素 
    while (!QueueEmpety(Q)){    
        printf("%c ", DeQueue(Q));  
    }    
    return 0;
}