STL（一）——stack栈及应用

栈特点：先进后出

STACK的六种基本操作

①bool empty();
如果当前堆栈为空，empty() 函数 返回 true 否则返回false.

②void pop();
pop() 函数移除堆栈中最顶层元素。

③void push( const TYPE &val );
push() 函数将 val 值压栈，使其成为栈顶的第一个元素。

④size_type size();
size() 函数返当前堆栈中的元素数目。

⑤TYPE &top();
top() 函数返回对栈顶元素的引用。

⑥“==” “<=” “>=” “<” “>” "!="
所有的这些操作可以被用于栈. 相等指栈有相同的元素并有着相同的顺序。

括号配对问题

算法思想：

1. 顺序扫描字符串，遇到左括号时候让该括号进栈；
2. 扫描到右括号时，比较该括号是否与栈顶元素匹配，若匹配则用pop（）将栈顶元素移出，继续判断；若不匹配，则配对次序不正确，匹配失败，直接退出；
3. 扫描到右括号而堆栈已为空，则右括号多于左括号，匹配失败，直接退出；
4. 字符串扫描结束时，若栈非空（即栈中还存在未匹配的左括号），说明左括号多于右括号，匹配失败；若栈为空，则匹配成功。

例1：对输入的一段字符串进行括号匹配检查，若语句中左括号和右括号数目相等，且能够完整的匹配成对，即不存在括号匹配上的错误，输出“OK”字样，否则输出“Wrong”字样。
样例输入：

)(
((())
()
(a)((b)((c)(d)))

样例输出：

Wrong
Wrong
OK
OK

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int main() {
  fio
  stack<char> small; 
  char s[10001];
  cin >> s;
  for (int i = 0; i < strlen(s); i++) {
    switch(s[i]) {
      case '(': small.push(s[i]);break;
      case ')': 
        if (!small.empty()) {
          small.pop();
          break;
        }
        if (small.empty()) {//栈中没有'('与之匹配
          cout << "Wrong"<< endl;
          return 0;
        }
    }
  }
  if (small.empty()) {
    cout << "OK" << endl;
  } else {//栈中还存在未配对的'('
    cout << "Wrong" << endl;
  }
}

例2：现在，有一行括号序列，请你检查这行括号是否配对。

输入：每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），数据保证S中只含有"[","]","(",")","{","}"六种字符

输出：每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出“OK”，如果不配对则输出“Wrong”

样例输入

{}[(]}
{[()]}
){}(

样例输出

Wrong
OK
Wrong

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
bool judge(char *p) {
  stack<char> s;
  while (*p) {
    if ((*p == '{') || (*p == '[') || (*p == '(')) {
      s.push(*p);
      p++;
    } else {
      if (s.empty())//若右括号多于左括号将会产生错误，p将指向非法区域，*p错误
        return false;
      if (s.top() == '{' && *p == '}' || s.top() == '[' && *p == ']'|| s.top() == '(' && *p == ')') {          
        s.pop();
        p++;
      } else {
        return false;
      }
    }
  }
  if (!s.empty()) return false;
  else return true;
}
int main() {
  fio
  char s[10001];
  cin >> s;
  if (judge(s)) cout << "OK" << endl;
  else cout << "Wrong" << endl;
}

表达式转换和求值问题

1、逆波兰表达式简介
核心思想：中缀表达式转换为后缀表达式。
中缀表达式：（9+6）* 7 - 8/2=====>>>>>>后缀表达式：9 6 + 7* 8 2 / -
优点：

1. 去除原来表达式中的括号，因为括号只指示运算顺序，不是完成计算必须的元素。
2. 后缀表达式不利于人阅读，但利于计算机处理。

2、将中缀表达式转换成后缀式（逆波兰表达式）

1. 从左到右读中缀表达式的每个字符。
2. 如果读到的字符为操作数，则直接输出到后缀表达式中。
3. 如果遇到“)”，则弹出栈内的运算符，直到弹出到一个“(”,两者相互抵消。（"("不打印）
4. “(”的优先级在栈内比任何运算符都小，任何运算符都可以压过它，不过在栈外却是优先级最高者。
5. 当运算符准备进入栈内时，必须和栈顶的运算符比较，如果外面的运算符优先级高于栈顶的运算符的优先级，则压栈；如果优先级低于或等于栈顶的运算符的优先级，则弹栈。直到栈顶的运算符的优先级低于外面的运算符优先级或者栈为空时，再把外面的运算符压栈。
6. 中缀表达式读完，如果运算符栈不为空，则将其内的运算符逐一弹出，输出到后缀表达式中。

   //比较l的优先级是否不高于r，r表示栈顶的符号
   bool priority(const char &l, const char &r) {
   if (r == '(')//左括号在栈外优先级最高
    return false;
   if (l == '+' || l == '-')
    return true;
   if ((l == '*' || l == '/') && (r == '*' || r == '/'))
    return true;
   return false;
   }
   //将中缀表达式转换成后缀式（逆波兰表达式）
   string change(const string &str) {
   vector<char> vec;
   string res;
   stack<char> st;//操作符栈
   for (int i = 0; i < str.length(); i++) {
    //如果是数字，直接输出到后序表达式中
    if (isdigit(str[i])) {
      vec.push_back(str[i]);
    } else {//如果是符号,需要与栈顶的元素进行比较
      if (st.empty() || str[i] == '(')//小括号在栈外优先级最高，直接压栈
        st.push(str[i]);
      else {
        //遇到右括号开始弹栈，直至左括号，两者相互抵消
        if (str[i] == ')') {
          while (!st.empty() && st.top() != '(') {
            vec.push_back(st.top());
            st.pop();
          }
          st.pop();//左括号不输出 
        } else {//遇到的是其他操作符
          if (priority(str[i], st.top())) {//优先级比栈顶元素低
            while (!st.empty()) {
              vec.push_back(st.top());
              st.pop();
            }
            st.push(str[i]);
          } else {//优先级比栈顶元素高，压栈
            st.push(str[i]);
          }
        }
      }
    }
   }
   while (!st.empty()) {//如果栈不为空，则将其中的元素全部弹出{
    vec.push_back(st.top());
    st.pop();
   }
   for (auto v : vec)
    res += v;
   return res;
   }

3、后缀表达式求值
后缀表达式具有和前缀表达式类似的好处，没有优先级的问题。

1. 直接读取表达式，如果遇到数字就压栈。
2. 如果遇到运算符，就弹出两个数进行运算，随后再将运算结果压栈。

double operate(double a, double b, char op) {
  double res = 0;
  switch (op) {
    case '+':
      res = a+b;break;
    case '-':
      res = a-b;break;
    case '*':
      res = a*b;break;
    case '/':
      res = a/b;break;
    default: break;
  }
  return res;
}
double calculate(string ss) {
  stack<double> st;//操作数堆栈
  for (auto &s : ss) {
    //如果是数字就压栈
    if (isdigit(s)) {
      st.push(s - '0');
    } else {//遇到字符就弹出两个操作数进行运算
      double a = st.top();
      st.pop();
      double b = st.top();
      st.pop();
      st.push(operate(b, a, s));
    }
  }
  return st.empty() ? 0 : st.top();//最后的结果为栈顶元素
}

主函数测试

int main() {
  string s = "(6+3)*7-5/2";
  string ss = change(s);
  cout << ss << endl;
  cout << calculate(ss) << endl;
}