首页 > 代码库 > 表达式计算

表达式计算

对于给定的字符串表达式 给出正确的答案。

 

首先我们要做的是识别这个表达式,即识别‘+‘. ‘-‘. ‘*‘. ‘/‘. 四则运算即数字。

其次我们要遵循运算表达式的优先级,像1-2*3直接顺序运算是不对的,乘法的优先级比减法高,注意识别括号。

 

数字识别我们用的是atof函数,将字符型转换成浮点型。

 

为了方便,我们此处要引入一个新的概念:后缀表达式。

 

所谓后缀表达式,即不考虑不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行。

如:(2 + 1) * 3 , 即2 1 + 3 *。

 

这样我们从左到右扫描,每遇到运算符就计算前两位数字。

 

我们用两个栈来模拟这个过程,对于输入的字符串s,从左到右扫描,遇到非数字则将前几位转换为浮点型储存在snum栈中,遇到运算符则取sch的栈顶运算符做前两位的运算,结果依旧放在snum栈中,在将现在的运算符放入sch栈中。

 

实行代码:

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 stack<char> sch;//储存运算符 
  5 stack<double> snum;//储存数字 
  6 
  7 char s[110],num[110]; 
  8 
  9 void cal_1(){//加减运算符在该程序中优先级最小,其前所有四则运算皆可进行 
 10     double n1,n2;
 11     
 12     char ch=sch.top();
 13     while(ch!=(){
 14     n1=snum.top();
 15     snum.pop();
 16     n2=snum.top();
 17     snum.pop();
 18         switch(ch){
 19             case+:
 20                 n2+=n1;
 21                 break;
 22             case-:
 23                 n2-=n1;
 24                 break;
 25             case*:
 26                 n2*=n1;
 27                 break;
 28             case/:
 29                 n2/=n1;
 30                 break;
 31         }
 32         //cout<<n2<<endl; 
 33         snum.push(n2);
 34         sch.pop();
 35         ch=sch.top();
 36     }
 37 }
 38 
 39 void cal_2(){//乘除的优先级比加减高,所以乘除前只可做同优先级的乘除运算 
 40     int n1,n2;
 41     char ch=sch.top();
 42     while(ch==*||ch==/){
 43         n1=snum.top();
 44         snum.pop();
 45         n2=snum.top();
 46         snum.pop();
 47         if(ch==*){
 48             n2*=n1;
 49         }
 50         else if(ch==/){
 51             n2/=n1;
 52         }
 53         //cout<<n2<<endl;
 54         snum.push(n2);
 55         sch.pop();
 56         ch=sch.top();
 57     }
 58     
 59 }
 60 
 61 int main(){
 62     gets(s);
 63     char c[2]="#"; //判断结束 
 64     strcat(s,c); 
 65     //cout<<s;
 66     sch.push(();//运算符前压如‘(‘ 防止对空栈操作 
 67     int k=0;
 68     double n;
 69     for(int i=0;s[i];i++){
 70         if(s[i]>=0&&s[i]<=9||s[i]==.){//当前位置为数字或.时计入num数组 
 71             num[k++]=s[i];
 72             continue;
 73         }
 74         num[k]=0;// 以0做标记,atof()只读取到这 
 75         if(num[0]!=0){
 76             n=atof(num);//将num数组里的数转换为一个浮点数 
 77             num[0]=0;
 78             snum.push(n);//将该数压入snum栈 
 79         }
 80         k=0;//计数器清零
 81         switch(s[i]){
 82             case+:
 83             cal_1();
 84             sch.push(+);
 85             break;
 86             
 87             case-:
 88             cal_1();
 89             sch.push(-);
 90             break;    
 91             
 92             case*:
 93             cal_2();
 94             sch.push(*);
 95             break;
 96             
 97             case/:
 98             cal_2();
 99             sch.push(/);
100             break;
101             
102             case(:
103             sch.push(();
104             break;
105             
106             case):
107             cal_1();
108             sch.pop();//去掉‘(‘ 
109             break;
110             
111             case#:
112             cal_1();
113             sch.pop();
114             break;
115             
116         }
117     }
118     printf("%.0lf",snum.top());  
119     return 0;
120 } 

 

表达式计算