计算(calc.cpp)
【问题描述】
小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)
【输入】
输入文件calc.in共1行，为一个算式。
【输出】
输出文件calc.out共1行，就是密码。
【输入样例】calc.in
1+(3+2)*(7^2+6*9)/(2)
【输出样例】calc.out
258
【限制】
100%的数据满足：算式长度<=30 其中所有数据在2^31-1的范围内。
用栈来处理运算顺序。把数和符号存在不同的栈中。每次读到数后检查已经入栈的运算符号，能算的就先算完。
如读到'^'，直接算出乘方结果压入栈中，而读到'*''/'要先检查下一个符号是不是'^'，不是的话才能算结果，加减同理……
以下的代码有一个已知的小bug：不支持自动消除空格（懒得写）读入的时候要是有空格，程序会爆炸。
代码（未使用STL）:
1 #include<iostream> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int a[200];//数栈 7 int p,i; 8 char sy[200],c[200];//符号栈 原算式
9 void push(){ 10 sy[++p]=c[i]; 11 } 12 void pp(){//弹栈运算 13 switch(sy[p--]){ 14 case '+':a[p]+=a[p+1];break; 15 case '-':a[p]-=a[p+1];break; 16 case '*':a[p]*=a[p+1];break; 17 case '/':a[p]/=a[p+1];break; 18 case '^':a[p]=pow(a[p],a[p+1]);break; 19 20 } 21 return; 22 } 23 int can(){//优先级判断 24 if((c[i]=='+'||c[i]=='-') && sy[p]!='(')return 1; 25 if((c[i]=='*'||c[i]=='/') && (sy[p]=='*' || sy[p]=='/'))return 1; 26 return 0; 27 } 28 int main(){ 29 p=1;i=0; 30 cin>>c; 31 c[strlen(c)]=')'; 32 sy[p]='('; 33 // 34 printf("test"); 35 while(i<strlen(c)){ 36 while(c[i]=='('){//处理左括号 37 push(); 38 i++; 39 } 40 int x=0; 41 while(c[i]>='0'&& c[i]<='9'){//处理数字 42 x=x*10+c[i++]-'0'; 43 } 44 a[p]=x; 45 do{ 46 if(c[i]==')'){//处理右括号 47 while(sy[p]!='(')pp(); 48 a[--p]=a[p+1]; 49 50 } 51 else{ 52 while(can())pp(); 53 push(); 54 } 55 i++; 56 }while(i<strlen(c) && c[i-1]==')'); 57 58 } 59 printf("%d",a[p]); 60 return 0; 61 }
代码（STL）:
STL真好用
1 /**/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<stack> 6 #include<cstring> 7 using namespace std; 8 char c[200]; 9 10 stack<int>num;//数 11 stack<char>sy;//符号 12 int pow1(int a,int b){//自写乘方 13 int i; 14 for(i=2;i<=b;i++){ 15 a*=a; 16 } 17 return a; 18 } 19 void mth(){//运算 20 int a,b; 21 char ch; 22 b=num.top(); 23 num.pop(); 24 a=num.top(); 25 num.pop(); 26 ch=sy.top(); 27 sy.pop(); 28 switch(ch){ 29 case '+': num.push(a+b);break; 30 case '-': num.push(a-b);break; 31 case '*': num.push(a*b);break; 32 case '/': num.push(a/b);break; 33 case '^': num.push(pow1(a,b));break; 34 default: break; 35 } 36 return; 37 } 38 int cmp(int ch){//优先级判断,没有严谨验证过，初步测试没有问题 //注释掉的那部分代码来自大神yhy，保证无误 39 if(sy.empty() || sy.top()=='(')return 0; 40 if(ch=='+' || ch=='-')return 1; 41 if(sy.top()=='^')return 1; 42 if((ch=='*' || ch=='/') && (sy.top()=='*' ||sy.top()=='/'))return 1; 43 return 0; 44 /* if (sy.empty()||sy.top()=='(') return 0; 45 if (sy.top()=='^') return 1; 46 if (ch=='^') return 0; 47 if (sy.top()=='*'||sy.top()=='/') return 1; 48 if (ch=='*'||ch=='/') return 0; 49 return 1;*/ 50 } 51 int main(){ 52 gets(c); 53 int len=strlen(c); 54 c[len]=')'; 55 sy.push('('); 56 int i; 57 for(i=0;i<=len;i++){ 58 if(c[i]=='('){ 59 sy.push('('); 60 continue; 61 } 62 if(c[i]>='0' && c[i]<='9') 63 { 64 int x=0; 65 while(c[i]>='0' && c[i]<='9'){ 66 x=x*10+c[i]-'0'; 67 i++; 68 } 69 i--; 70 num.push(x); 71 continue; 72 } 73 if(c[i]==')'){ 74 while(sy.top()!='(')mth(); 75 sy.pop(); 76 continue; 77 } 78 while(cmp(c[i]))mth(); 79 sy.push(c[i]); 80 } 81 while(!sy.empty())mth(); 82 printf("%d ",num.top()); 83 return 0; 84 }