计算(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 其中所有数据在231-1的范围内。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<string>
4 #include<cstring>
5 #include<cmath>
6 using namespace std;
7 int number[101],i=0, p=1;
8 char symbol[101],s[256],t[256];
9 //p:指向当前的运算符,同时指向当前运算符所对应的操作数
10 void push() //算符入栈运算
11 {
12 symbol[++p]=s[i];
13 }
14 void pop() //运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算
15 {
16 switch (symbol[p--])//运算完成之后扔掉运算符,也标志着需要运算的数已经运算完成
17 {
18 case '+':
19 {
20 number[p]+=number[p + 1];
21 break;
22 }
23 case '-':
24 {
25 number[p]-=number[p + 1];
26 break;
27 }
28 case '*':
29 {
30 number[p]*=number[p + 1];
31 break;
32 }
33 case '/':
34 {
35 number[p]/=number[p + 1];
36 break;
37 }
38 case '^':
39 {
40 number[p]=pow(number[p],number[p + 1]);
41 }
42 }
43 }
44 bool can() //判断运算符的优先级别,建立标志函数,能否进行运算
45 {
46 if ((s[i]=='+'||s[i]=='-')&&symbol[p]!='(') //在括号之内
47 return 1;
48 if ((s[i]=='*'||s[i]=='/')&&(symbol[p]=='*'||symbol[p]=='/'))
49 //若遇到乘除且p对应的恰好是乘除
50 return 1;
51 return 0;
52 }
53 main()
54 {
55 printf("String :");gets(s);
56 s[strlen(s)]=')';
57 symbol[p]='(';
58 while (i<strlen(s))
59 {
60 while (s[i]=='(') //左括号处理,压入左括号,有了左括号才能进行与右括号的匹配 while (symbol[p]!='(')
61 {
62 push();
63 i++;
64 }
65 int x=0;
66 while (s[i]>='0'&&s[i]<='9') //取数入操作数栈
67 x=x*10+s[i++]-'0';
68 number[p]=x;
69 do
70 {
71 if (s[i]==')') //当右括号后面还有右括号时处理
72 {
73 while (symbol[p]!='(')
74 pop();//当括号内还有算式没有算完时进行运算
75 number[--p]=number[p + 1];//当运算完成以后左括号已经没有意义,所以将指针p移向前一个运算符,并复制所得的结果
76 }
77 else
78 { //根据标志函数值作运算符入栈或出栈运算处理
79 while (can())
80 pop();// 当可以进行运算时运算,然后压入一个运算符
81 push();
82 }
83 i++;
84 }while (i<strlen(s)&&s[i-1]==')');//当检测到右括号时,可以运算括号内的内容
85 }
86 printf("Result=%d", number[0]);//因为所有的运算全部是建立在括号之内的,所以随着运算符的减少(运算符减少同时标志着需要操作的数减少)和最后的p--,结果一定保存在number[0]内
87 return 0;
88 }