37.2° Blog

1.括号匹配

/**
 * 括号匹配
*/
bool bracketCheck(char str[], int len)
{
    SqStack S;
    initStack(S);
    for(int i = 0; i < len; i++)
    {
        if(str[i] == '(' || str[i] == '[' || str[i] == '{')
        {
            push(S, str[i]);    // 左括号，入栈
        }
        else
        {
            if(stackEmpty(S))   // 右括号，当前栈空，匹配失败
                return false;
            char 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);   // 检索完全部括号，栈空说明匹配成功
}

2.表达式求值

2.1 三种表达式

• 中缀表达式：；运算符在操作数中间
• 后缀表达式（逆波兰式）：运算符在操作数后面
• 前缀表达式（波兰式）：运算符在操作数前面

2.2 后缀表达式

（1）计算

从左往右扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈。

注意：先弹出的元素是“右操作数”

（2）中缀转后缀

1. 按“左优先”原则确定运算符的运算次序
2. 根据1中确定的次序，依次将各个运算符和与之相邻的两个操作数<左操作数 右操作数 运算符>的规则合体

（3）后缀转中缀

从左往右扫描，每遇到一个运算符，就将 <左操作数 右操作数 运算符>变为（左操作数 运算符 右操作数）的形式

2.3 前缀表达式

（1）计算

从右往左扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈

注意：先弹出的元素是“左操作数”

（2）中缀转前缀

1. 按“右优先”原则确定运算符的运算次序
2. 根据1中确定的次序，依次将各个运算符和与之相邻的两个操作数按<运算符 左操作数 右操作数> 的规则合体