[Codevs 1107][NOIP 1107]等效表达-白红宇

[Codevs 1107][NOIP 1107]等效表达

阅读量：6124 次

发布时间：2019-06-21

本文共 3539 字，大约阅读时间需要 11 分钟。

主题连接：

一道非常奇妙的题目。

对于算术表达式一类的问题，能够採用编译原理里的后缀表达式的方式来做。详细做法是分别维护两个栈，一个栈里保存表达式里的数字，还有一个栈里保存表达式里的运算符，给每种运算符一个优先级，我们要维护这个栈的单调性，每次读入运算符中的数字或运算符，读入的是运算符时，若这个运算符比栈顶的运算符优先级低，就弹出栈顶元素。把栈顶的运算符和数字栈里栈顶的两个数字拿出来做一次运算，运算结果再入数字栈。直到运算符栈的栈顶元素优先级比这个运算符低为止。

然后题目有坑点，一是读入的表达式字符串可能有空格，所以不能直接scanf一次搞定读入数据操作。二是推断表达式是否等价时，带入的值假设不好可能会WA，所以为了避免这样的情况的发生，我们代入的数字应该是个小数，用三态函数推断表达式结果是否相等，多代入几个小数计算。基本上不可能出现意外WA的发生。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #define MAXN 1000#define EPS (1e-5)using namespace std;long long stackOfNum[MAXN];int topNum=0; //保存数字的栈和栈顶下标char stackOfSign[MAXN];int topSign=0; //保存运算符号的栈和栈顶下标bool needPop[50][50]; //needPop[i][j]=true表示当前运算符为i,栈顶运算符为j时须要出栈bool isTrue[30];int dcmp(long long a,long long b) //a>b return 1; a=b return 0; a
            b) return 1; return -1;}long long cal(long long a,long long b,char cmd){ switch(cmd) { case '^': { long long ans=1; for(int i=1;i<=(int)b;i++) ans*=a; return ans; } case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; } return 0;}long long getAns(char s[],int len,long long a) //将表达式的值求出来，len=表达式长度,a=字母a相应的值{ int p=1; //指针指向当前的表达式下标 topNum=0; topSign=0; while(p<=len) { while(s[p]==' ') p++; if(p>len) break; if(s[p]>='0'&&s[p]<='9') //是数字 { int nowNum=0; while(p<=len) { if(!(s[p]>='0'&&s[p]<='9')) //如今的s[p]不是数字了 break; nowNum*=10; nowNum+=s[p]-'0'; p++; } stackOfNum[++topNum]=nowNum; //这个数字进栈 continue; } else if(s[p]=='a') stackOfNum[++topNum]=a; //假设是a，将a相应的数字压入栈 else //s[p]是个运算符,将栈中全部比它优先级 { while(topSign>0&&topNum>0) { if(needPop[s[p]][stackOfSign[topSign]]) { if(stackOfSign[topSign]=='(') //右括号遇到左括号 { topSign--; break; } stackOfNum[topNum-1]=cal(stackOfNum[topNum-1],stackOfNum[topNum],stackOfSign[topSign]); topNum--; topSign--; } else break; } if(s[p]!=')') stackOfSign[++topSign]=s[p]; } p++; } while(topSign>0&&topNum>1) { stackOfNum[topNum-1]=cal(stackOfNum[topNum-1],stackOfNum[topNum],stackOfSign[topSign]); topNum--; topSign--; } return stackOfNum[topNum];}int main(){ memset(isTrue,true,sizeof(isTrue)); //先打个巨表~！ needPop['^']['^']=true; needPop['^']['+']=false; needPop['^']['-']=false; needPop['^']['*']=false; needPop['^']['/']=false; needPop['^']['(']=false; //---------------------- needPop['+']['^']=true; needPop['+']['+']=true; needPop['+']['-']=true; needPop['+']['*']=true; needPop['+']['/']=true; needPop['+']['(']=false; //---------------------- needPop['-']['^']=true; needPop['-']['+']=true; needPop['-']['-']=true; needPop['-']['*']=true; needPop['-']['/']=true; needPop['-']['(']=false; //---------------------- needPop['*']['^']=true; needPop['*']['+']=false; needPop['*']['-']=false; needPop['*']['*']=true; needPop['*']['/']=true; needPop['*']['(']=false; //---------------------- needPop['/']['^']=true; needPop['/']['+']=false; needPop['/']['-']=false; needPop['/']['*']=true; needPop['/']['/']=true; needPop['/']['(']=false; //---------------------- needPop['(']['^']=false; needPop['(']['+']=false; needPop['(']['-']=false; needPop['(']['*']=false; needPop['(']['/']=false; needPop['(']['(']=false; //---------------------- needPop[')']['^']=true; needPop[')']['+']=true; needPop[')']['-']=true; needPop[')']['*']=true; needPop[')']['/']=true; needPop[')']['(']=true; char s[MAXN]; int n; long long trueAns1,trueAns2,nowAns1,nowAns2; //trueAns=带入a值后应该得到的答案，nowAns=选择选项中带入a值得到的答案 //scanf("%s",s+1); gets(s+1); trueAns1=getAns(s,strlen(s+1),1.4); trueAns2=getAns(s,strlen(s+1),2.8); scanf("%d",&n); gets(s+1); for(int i=0;i

转载地址：http://wnfua.baihongyu.com/

你可能感兴趣的文章