数据结构——栈的应用

1.用数组实现括号的匹配

#include
bool compare()
{
    char  str1[10] = { '{','{','(',')','}','}' };    //准备判定的数组
    char  str2[10] = {};   //存放左括号的数组
 
    int top2 = -1;      //标记str2数组的下标
    for (int i = 0; i < 6; i++)          //循环6个待判定的括号
    {
        if (str1[i] == '{' || str1[i] == '(' || str1[i] == '[')   //判断是否为左括号
        {
            top2++;
            str2[top2] = str1[i];
        }
        else                                               
        {
            if (top2 == -1)                           //判断左括号数组是否为空 为空的话右括号没得匹配
            {
                return false;
            }
            else                                    //判断是否匹配
            {
                if (str1[i] == '}' && str2[top2] != '{')
                    return false;
                if (str1[i] == ')' && str2[top2] != '(')
                    return false;
                if (str1[i] == ']' && str2[top2] != '[')
                    return false;
                top2--;                      //匹配完逻辑上去除左括号里的数
            }
        }
    }
    if (top2 != -1)                         //判断左括号数组是否为空 如果全部匹配完 还剩下左括号没得匹配的
        return false;
    return true;
}
int main()
{
    bool ret;
    ret = compare();             //接收函数返回值
    if (ret)
        printf("succeed");         //成功
    else
        printf("fail");          //失败
    return 0;
}

2.用栈实现括号匹配

用栈实现括号匹配: 依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。 匹配失败情况: ①左括号单身②右括号单身③左右括号不匹配 

 bool bracketMatching(char str[],int length){
  SqStack S;
  initStack(&S);
  for(int i=0;i 

 
二、栈在表达式求值中的应用 
1、中缀、后缀、前缀表达式
 
 
 
2、中缀表达式转后缀表达式（手算)
 
 
 
 
 
这种是机算的果 很适合验证答案
 
注: “左优先”原则，不要FreeStyle，保证手算和机算结果相同“左优先”原则:
 
只要左边的运算符能先计算，就优先算左边的
 
3、后缀表达式的计算（手算)
 
 
 
 
 
 
 
 
后缀表达式的手算方法: 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运合体为一个操作数 注意:两个操作数的左右顺序
 
4、后缀表达式的计算（机算)
 
用栈实现后缀表达式的计算: ①从左往右扫描下一个元素,直到处理完所有元素
 
②若扫描到操作数则压入栈,并回到①；否则执行
 
③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①
 
 
 
 
 
答案：5
 
5、中缀表达式转前缀表达式（手算）
 
 
 
注：后缀表达式用栈运算时 先弹出的元素是“右操作数”
 
前缀表达式用栈运算时 先弹出的元素是“左操作数”
 
6、中缀表达式转后缀表达式(机算)
 
 
 
 
 
 
 
7、中缀表达式的计算(用栈实现)
 
用栈实现中缀表达式的计算: 初始化两个栈，操作数栈和运算符栈
 
若扫描到操作数，压入操作数栈
 
若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈) 结合6中的内容
 
 
 
总结
 
 
 
三、栈在递归中的应用