括号匹配算法
利用栈先进后出的特性，思路分三步：
1.遇到左括号，直接入栈，继续向后遍历；
2.遇到右括号，
(1).如果栈为空，说明无对应左括号，则返回表达式不匹配；
(2).如果栈不为为空，将栈顶元素弹出判断是否是相匹配的括号；
如果匹配，将栈顶元素弹出，继续遍历；如果不匹配，说明不是同类括号，直接返回表达式不匹配。
3.遍历到表达式末尾，如果栈中有剩余元素，说明存在多余左括号，返回表达式不匹配；如果栈为空，返回表达式匹配。
测试样例：
//(56-20)/(4+2)//9 * (10 + 11 * (12 + 13)) + 14//(15 + 16) * (17 + 18 * (19 + 20)//((21 + 22) * 23 + (24 * 25)) + 26 * 27)) + 28//{asdsd{ddads}sa}[]sassada[]sda{{aassaddsd[]}dsad}
完整程序实现如下：
#include<bits/stdc++.h>using namespace std;bool judge(char str[]){stack<char> s;int n = strlen(str);for(int i = 0; i < n; i++){if(str[i]=='(') s.push(str[i]);//左括号入栈 if(str[i]=='[') s.push(str[i]);if(str[i]=='{') s.push(str[i]);if(str[i]==')'){if(s.empty()) return false;//无左括号不匹配 else if(s.top()=='(') s.pop();//匹配 else return false;//不是同类括号 }if(str[i]==']'){if(s.empty()) return false;else if(s.top()=='[') s.pop();else return false;}if(str[i]=='}'){if(s.empty()) return false;else if(s.top()=='{') s.pop();else return false;}}return s.empty();//空匹配 非空说明存在多余左括号 }int main(){char str[10000];cin>>str; //(56-20)/(4+2)//9 * (10 + 11 * (12 + 13)) + 14//(15 + 16) * (17 + 18 * (19 + 20)//((21 + 22) * 23 + (24 * 25)) + 26 * 27)) + 28//{asdsd{ddads}sa}[]sassada[]sda{{aassaddsd[]}dsad}bool v = judge(str);if(v) cout<<"匹配"<<endl;else cout<<"不匹配"<<endl;return 0;}
简单计算器实现：设计一个计算器，实现加减乘除和小括号的计算。
设计思路：构建两个栈，一个压入要进行计算的数字，一个压入运算符，运算符涉及到优先级问题，括号>乘除>加减。遍历要计算的字符串，数字压入栈num，运算符压入栈s：
1.如果栈s为空，直接将运算符压入栈s；
2.如果栈s不为空，且栈顶运算符优先级大于等于待入栈运算符，将栈顶运算符弹出，从栈num弹出两个数字，进行运算，将计算结果压入栈num，直至栈空或栈顶运算符优先级小于待入栈运算符，将待入栈元素入栈；
3.如果栈s不为空，且栈顶运算符优先级小于待入栈运算符，直接将待入栈运算符入栈；
4.遇到左括号直接入栈，重复2，3步骤，遇到右括号时，若栈s栈顶运算符为左括号，直接将左括号弹出；若不为左括号，将运算符依次弹出进行运算，直至栈顶运算符为左括号，将其弹出。
5.字符串遍历完成后，若栈s为空，栈num栈顶元素即运算结果；栈s不为空，将运算符依次弹出进行计算。
涉及程序时，我们先写一个函数prio来返回运算符的优先级，加减返回1，乘除返回2，小括号返回3和4。
int prio(char ch){switch(ch){case '+':case '-':return 1;case '*':case '/':return 2;case'(':return 3;case ')':return 4;}}
再写一个运算函数：
int cal(int a,int b,char ch){switch(ch){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;}}
上述5步我们慢慢拆分：
首先是遍历字符串：
for(int i=0;i<n;i++)
数字入栈：
if('0'<=str[i]&&str[i]<='9'){x = x*10+(str[i]-'0'); v=1;}if(str[i]>'9'||str[i]<'0'||i==n-1){if(v==1){num.push(x);//cout<<"push:"<<x<<endl;x=0;}v=0;}
加v标记的原因是如果多个运算符相连，会导致压入不必要的数字0。
运算符入栈：
if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='('||str[i]==')'){
1.如果栈s为空，直接将运算符压入栈s；
if(s.empty()) s.push(str[i]);
2.如果栈s不为空，且栈顶运算符优先级大于等于待入栈运算符，将栈顶运算符弹出，从栈num弹出两个数字，进行运算，将计算结果压入栈num，直至栈空或栈顶运算符优先级小于待入栈运算符，将待入栈元素入栈；
while(!s.empty()&&prio(s.top())>=prio(str[i])&&s.top()!='('){int x2 = num.top();num.pop();int x1 = num.top();num.pop();char ch = s.top();s.pop();//cout<<x1<<ch<<x2<<" "<<cal(x1,x2,ch)<<endl;num.push(cal(x1,x2,ch));}
3.如果栈s不为空，且栈顶运算符优先级小于待入栈运算符，直接将待入栈运算符入栈；
s.push(str[i]);
4.遇到左括号直接入栈，重复2，3步骤，遇到右括号时，若栈s栈顶运算符为左括号，直接将左括号弹出；若不为左括号，将运算符依次弹出进行运算，直至栈顶运算符为左括号，将其弹出。
if(str[i]=='('){s.push(str[i]);continue;}if(str[i]==')'){while(!s.empty()&&s.top()!='('){int x2 = num.top();num.pop();int x1 = num.top();num.pop();char ch = s.top();s.pop();//cout<<x1<<ch<<x2<<" "<<cal(x1,x2,ch)<<endl;num.push(cal(x1,x2,ch));}s.pop();continue;}
5.字符串遍历完成后，若栈s为空，栈num栈顶元素即运算结果；栈s不为空，将运算符依次弹出进行计算。
while(!s.empty()){int x2 = num.top();num.pop();int x1 = num.top();num.pop();char ch = s.top();s.pop();//cout<<x1<<ch<<x2<<" "<<cal(x1,x2,ch)<<endl;num.push(cal(x1,x2,ch));}return num.top();
完整程序实现如下：
#include<bits/stdc++.h>using namespace std;int prio(char ch){switch(ch){case '+':case '-':return 1;case '*':case '/':return 2;case'(':return 3;case ')':return 4;}}int cal(int a,int b,char ch){switch(ch){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;}}int calculation(char str[]){stack<char> s;stack<int> num;int n = strlen(str);int x = 0;//用于提出字符串数字 int v = 0;//用于判断何时将数字压入栈 for(int i=0;i<n;i++){//cout<<str[i]<<endl;if('0'<=str[i]&&str[i]<='9'){x = x*10+(str[i]-'0'); v=1;}if(str[i]>'9'||str[i]<'0'||i==n-1){if(v==1){num.push(x);//cout<<"push:"<<x<<endl;x=0;}v=0;}if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='('||str[i]==')'){if(str[i]=='('){s.push(str[i]);continue;}if(str[i]==')'){while(!s.empty()&&s.top()!='('){int x2 = num.top();num.pop();int x1 = num.top();num.pop();char ch = s.top();s.pop();//cout<<x1<<ch<<x2<<" "<<cal(x1,x2,ch)<<endl;num.push(cal(x1,x2,ch));}s.pop();continue;}if(s.empty()) s.push(str[i]);else {//cout<<s.top()<<" "<<str[i]<<endl;while(!s.empty()&&prio(s.top())>=prio(str[i])&&s.top()!='('){int x2 = num.top();num.pop();int x1 = num.top();num.pop();char ch = s.top();s.pop();//cout<<x1<<ch<<x2<<" "<<cal(x1,x2,ch)<<endl;num.push(cal(x1,x2,ch));}s.push(str[i]);}}}while(!s.empty()){int x2 = num.top();num.pop();int x1 = num.top();num.pop();char ch = s.top();s.pop();//cout<<x1<<ch<<x2<<" "<<cal(x1,x2,ch)<<endl;num.push(cal(x1,x2,ch));}return num.top();}int main(){char str[10000];cin>>str; //(56-20)/(4+2)//9*(10+11*(12+13))+14//(15+16)*(17+18*(19+20))//(((21+22)*23+(24*25))+26*27)+28//10+11*12/12+14-1+2*3*1-5/5*5-5-5-5*5/5*5/5//10+11-12/12+14-1+22/2*5int cnt = calculation(str);cout<<cnt;return 0;}
也有想过对输入的字符串进行一个合法性的判断，括号匹配，正确的运算符，这两个判断可以简单实现，但下面这两种
1234-1234+-3412+231*41-
感觉判断起来有些许繁琐，但不判断程序又显得不完美，小记录一下。多给给几组测试样例，因为是整数相除，所以尽量选择整除的数：
//(56-20)/(4+2)//9*(10+11*(12+13))+14//(15+16)*(17+18*(19+20))//(((21+22)*23+(24*25))+26*27)+28//10+11*12/12+14-1+2*3*1-5/5*5-5-5-5*5/5*5/5//10+133+(4+22)/2*5//10+11-12/12+14-1+22/2*5
有问题敬请大家指正。
