因为最近在学编译原理，老师布置了个恶心的东西就是正则表达式的题目，所以用户到了字符匹配的运算，先温习一下四则运算的栈方法实现
主要是俩个栈 一个用来保存数字 一个用来保存操作符
#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
using namespace std;
stack <int> num;//存数字
stack <char> p;//存操作符
void init()
{while(!num.empty())num.pop();while(!p.empty())p.pop();p.push('#');
// cout<<p.top();
}
int cal(char x,int a,int b)
{switch(x){case '+':return a+b;case '-':return b-a;case '*':return a*b;case '/':return b/a;}
}
char cmp(char x,char y)
{switch(x){case '+':case '-': if (y == '+' || y == '-' || y == '*' || y == '/') return '<'; //扫描的小于栈顶 else return '>'; //扫描的大于栈顶 break; case '*': case '/': if (y == '*' || y == '/') return '<'; else return '>'; break; case '(':
// if(y == ')'){
// printf("输入有误!\n"); exit(-1);
// } return '>'; break; case ')':
// if (y == '(')
// return '='; else if(y == '#'){ printf("输入有误!\n"); exit(-1); }
// else{
// return '<';
// }return '~'; break; case '#': return '<'; } }
int main()
{char s[1000];//中缀表达式while(scanf("%s",s)!=EOF)//不检查输入的问题 {init();int len = strlen(s);for(int i=0;i<len;i++){if(s[i]>=48&&s[i]<=57)//是数字{int sum = 0;while(s[i]>=48&&s[i]<=57){sum = sum*10+s[i]-'0';i++;}i--;
// printf("%d ",sum);num.push(sum);continue;}else {char x = cmp(s[i],p.top());
// printf("%c ",x);if(x=='>')//当前操作符大于栈顶 {p.push(s[i]);continue;}else if(x=='<'){while(x=='<'){//先取数 int a = num.top();num.pop();int b = num.top();num.pop();//计算 int v = cal(p.top(),a,b);//num.push(v);//操作数退出
// printf("%d",v);p.pop();//继续比较 x = cmp(s[i],p.top());}p.push(s[i]);continue;}else if(x=='~')//遇到右括号 需要计算括号内的值 {//说明当前要运算括号内的x = p.top();while(x!='('){int a = num.top();num.pop();int b = num.top();num.pop();//计算 int v = cal(p.top(),a,b);//num.push(v);//操作数退出 p.pop();x = p.top();}p.pop();//退出( continue; }} } char op = p.top();
// printf("%c",p.top());while(op!='#'){int a = num.top();num.pop();int b = num.top();num.pop();//计算 int v = cal(p.top(),a,b);//num.push(v);//操作数退出 p.pop();op = p.top();}printf("%d\n",num.top());}
}