[数据结构与算法]栈的简单应用---括号匹配和表达式（逆波兰表达式和中缀表达式）的计算

1.括号匹配

算法思路：从左往右依次扫描括号串，如果遇到左括号串如 (, [ ,{ ，将它们入栈，如果遇到右括号串如 ) , ], } , 则从栈中出栈一个左括号，并检测是否于该右括号匹配。该思路有三种不匹配的情况，一是括号不匹配，二是扫到右括号时左括号栈已经为空，三是整个字符串扫描完毕后，左括号栈中依然还有左括号未出栈。如果以上三种情况都不满足，则说明该括号串是匹配的

/*
 * 判断括号字符串是否匹配
 * */
#include<iostream>
#include<string>
#include<cstdio>
#include<stack>
using namespace  std;
stack<char> sc;//存储左括号的栈
bool judge(string s) {
    for (int i = 0; i < (int) s.size(); i++) {
        //扫描到左括号直接将其入栈
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            sc.push(s[i]);
        } else {
            //如果扫描到右括号),],}而栈是空的，那么匹配失败
            if (sc.empty())return false;
            char elem = sc.top();//左括号栈出栈一个
            sc.pop();
            //检测左右括号是否匹配
            if (s[i] == ')' && elem != '(')return false;
            if (s[i] == ']' && elem != '[')return false;
            if (s[i] == '}' && elem != '{')return false;
        }
    }
    return sc.empty();//检索完全部括号，栈空则说明匹配成功
}
int main(){
string str;
while(cin>>str){
      if(judge(str)) {
          cout<<"success"<<endl;//匹配成功
      }else {
          cout<<"failed"<<endl;//匹配失败
      }
    }
return 0;
}

2. 计算后缀表达式

/*
 * 计算后缀表达式
 * */
#include<bits/stdc++.h>
using namespace  std;
stack<int> si;//操作数栈
int main(){
    string s;//后缀表达式
    while(cin>>s) {
      for(int i = 0;i<(int)s.size();i++){
            //扫描整个后缀表达式，如果扫到操作数，那么直接将其入栈
            if(s[i]>='0'&& s[i]<='9'){
                si.push(s[i]-'0');
            }
            else if(s[i]=='+'){
                int x = si.top();
                si.pop();//出栈
                int y = si.top();
                si.pop();
                int sum  = x + y;
                si.push(sum);//将计算结果压入栈中
            }
            else if(s[i]=='-') {
                int x = si.top();//右操作数
                si.pop();//出栈
                int y = si.top();//左操作数
                si.pop();
                int sum = y - x;// - 和 / 要注意运算的顺序
                si.push(sum);//将计算结果压入栈中
            }
            else if(s[i]=='*') {
                int x = si.top();
                si.pop();//出栈
                int y = si.top();
                si.pop();
                int sum = x * y;
                si.push(sum);//将计算结果压入栈中
            }
            else if(s[i]=='/') {
                int x = si.top();
                si.pop();//出栈
                int y = si.top();
                si.pop();
                int sum = y / x;
                si.push(sum);//将计算结果压入栈中
            }
      }
      //操作数栈的栈顶（最后一个数）就是最终的结果
      cout<<si.top()<<endl;
    }
    return 0;
}

3.中缀表达式转为后缀表达式

注意这里是以A和B代替两个操作数，输入的中缀表达式形如A+B等

#include<bits/stdc++.h>
using namespace std;
stack<char> st;
map<char,int> mp;//使用map数组标志运算符的权值
int main(){
//乘除的权值大于加减的权值
mp['+'] = mp['-'] = 1;
mp['*'] = mp['/'] = 2;
string s;//输入的中缀表达式
string str;//输出的后缀表达式
while(cin>>s){
    str = "";
    for(int i = 0;i<(int)s.size();i++){
        //从左往右进行扫描，如果遇到操作数，直接写入后缀表达式
        if(s[i]>='A'&&s[i]<='Z'){
            str+=s[i];
        }
        else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'){
                //依次弹出栈中优先级高于或等于当前运算符的所有运算符
               while(!st.empty()&&mp[st.top()]>=mp[s[i]]){
                    str+=st.top();//加入后缀表达式
                    st.pop();
               }
               //注意要把当前的运算符入栈
               st.push(s[i]);

        }
        //如果扫描到"("直接将其出栈
        else if(s[i]=='('){
               st.push(s[i]);
        }
        //依次从栈中弹出运算符并加入到后缀表达式，直到弹出'('位置
        else if(s[i]==')'){
                while(st.top()!='('){
                     str+=st.top();
                     st.pop();
                }
                st.pop();//注意要把'('出栈，但不加入后缀表达式
        }
    }
    //注意还要把栈中剩下的运算符出栈
    while(!st.empty()){
        str+=st.top();
        st.pop();
    }
    cout<<str<<endl;
}
return 0;
}

4. 中缀表达式的计算

中缀表达式的计算可以理解为中缀表达式转为后缀表达式的算法和后缀表达式计算的算法的结合，中缀表达式匹配人类的认知，适合手算，而对于计算机更适合计算后缀表达式

/*
 * 计算中缀表达式，就是将中缀转后缀和后缀表达式计算两种算法结合
 * */
#include<bits/stdc++.h>
using namespace  std;
stack<char> sc;//操作符栈
stack<int> si;//操作数栈
map<char,int> mp;//权值map
//计算函数
void calc(char c){
    if(c=='+'){
        int x = si.top();//弹出右操作数
        si.pop();
        int y = si.top();//弹出左操作数
        si.pop();
        int sum = x + y;
        si.push(sum);//将运算结果再压回栈中
    }
    else if(c=='-'){
        int x = si.top();//弹出右操作数
        si.pop();
        int y = si.top();//弹出左操作数
        si.pop();
        int sum = y - x;//注意运算顺序
        si.push(sum);//将运算结果再压回栈中
    }
    else if(c=='*'){
        int x = si.top();//弹出右操作数
        si.pop();
        int y = si.top();//弹出左操作数
        si.pop();
        int sum = y * x;
        si.push(sum);//将运算结果再压回栈中
    }
    else if(c=='/'){
        int x = si.top();//弹出右操作数
        si.pop();
        int y = si.top();//弹出左操作数
        si.pop();
        int sum = y / x;
        si.push(sum);//将运算结果再压回栈中
    }


}

int main() {
    //权值
    mp['+'] = mp['-'] = 1;
    mp['*'] = mp['/'] = 2;
    string s;
    while (cin >> s) {
        for (int i = 0; i < (int) s.size(); i++) {
            //如果扫描到操作数，就直接入操作数栈
            if (s[i] >= '0' && s[i] <= '9') {
                si.push(s[i] - '0');
            }
            else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
                //依次弹出栈中优先级高于或等于当前运算符的所有运算符
                while (!sc.empty() && mp[sc.top()] >= mp[s[i]]) {
                    calc(sc.top());//在弹出运算符的同时，操作数栈也应该弹出两个操作数进行对应的运算，并将运算结果重新压入栈中
                    sc.pop();
                }
                sc.push(s[i]);//注意还要将扫描到的运算符入栈
            }
            //扫描到"("，直接将其入操作符栈
            else if(s[i]=='('){
                   sc.push(s[i]);
            }
            else if(s[i]==')'){
                   if(sc.top()!='('){
                       calc(sc.top());
                       sc.pop();
                   }
                   sc.pop();//注意将“（”出栈
            }
        }
        //注意还要把运算符栈中剩余的运算符出栈
        while(!sc.empty()){
            calc(sc.top());
            sc.pop();
        }
        //输出栈顶元素就是答案
        cout<<si.top()<<endl;

    }
    return 0;
}