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中确定的次序,依次将各个运算符和与之相邻的两个操作数<左操作数 右操作数 运算符>的规则合体

(3)后缀转中缀
从左往右扫描,每遇到一个运算符,就将 <左操作数 右操作数 运算符>变为(左操作数 运算符 右操作数)的形式
2.3 前缀表达式
(1)计算
从右往左扫描,遇到操作数入栈,遇到运算符则弹出两个栈顶元素运算后入栈
注意:先弹出的元素是“左操作数”

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