首页 > ACM题库 > HDU-杭电 > hdu 2556 Simple Desk Calculator-数据结构[解题报告]C++
2014
02-10

hdu 2556 Simple Desk Calculator-数据结构[解题报告]C++

Simple Desk Calculator

问题描述 :

Your task are to write a program that imitates a simple desk calculator. Your calculator must be able to accept an infix expression which at least includes (, ), +, -, *, /,% . If the expression is legal, output its value, else ouput an error message.

输入:

There are several test cases, each occupies one line that contains an infix expression. Proceed until the end of the file.

输出:

There are several test cases, each occupies one line that contains an infix expression. Proceed until the end of the file.

样例输入:

4.99+5.99+6.99*1.06
(3*5*(4*8)%2)
1+2(
2/0
2.5%2
2%2.5

样例输出:

18.39
0.00
ERROR IN INFIX NOTATION
ERROR IN INFIX NOTATION
ERROR IN INFIX NOTATION
ERROR IN INFIX NOTATION

又是一道中缀表示法的表达式求值问题,不过比起昨天的“简单计算器”,这道题的难度有所增加。首先是表达式中允许出现括号和求模运算,而且允许出现double型的操作数(非负的),最复杂的可能是表达式不保证合法,也就是说写出的程序必须有判断表达式是否合法的能力。

乍一看这题,我被狠狠的震慑住了,有点不知从何下手的感觉。经过分析,觉得基本的算法不用改变,只需增加若干功能函数或者补全细节,应该可以满足要求。

最后事实说明我的思路基本靠谱,而且运气也不错,交到第二遍就Accept(本来我是已经做好了人肉交题的思想准备了用栈实现表达式求值(2):Simple Desk Calculator - oldsharp - Joker

还想说一下的是,本题的测试数据还不够全面(纯属个人观点)。比如”8++”这组数据,我的程序将它判为格式错误,而Zerob13的代码跑这个数据时会崩溃;又如”(()(5+8)”这样的数据,我的代码判为合法,而Zerob13的代码判为非法;再如”5+.5″,我的判非法,Zerob13的判合法。同为AC代码,却存在很多的差异,说明测试数据没有包括以上情况,我也不清楚某些情况究竟是合法还是非法。还有就是类似于”1*0/(5-6)”这样的数据,我的代码输出-0.00,而zerob13的代码输出的是0.00,我不明白这里的差异是如何造成的。

贴一下我的代码:

#include<iostream>
#include<cstring>
#include<cctype>
#include<stack>
using std::stack;
const int L=1001;

stack<double> OPND;
stack<char> OPTR;

bool IsLegalChar(char c)
{
    if(isdigit(c))
       return true;
    else if(c=='+' || c=='-' || c=='*' || c=='/' || c=='%' || c=='(' || c==')' || c=='.')
       return true;
    else
       return false;
}

double ToOperand(char t[],int length,int count,int point)
{
    if(count>1 || t[0]=='.' || t[length-1]=='.')
       return -1.0;
    double result=0.0,v=1.0;
    if(count==0)
    {
       for(int i=length-1;i>=0;i--)
       {
           result+=(double)(t[i]-'0')*v;
           v*=10;
       }
       return result;
    }
    else
    {
       for(int i=point-1;i>=0;i--)
       {
           result+=(double)(t[i]-'0')*v;
           v*=10;
       }
       v=0.1;
       for(int i=point+1;i<length;i++)
       {
           result+=(double)(t[i]-'0')*v;
           v/=10.0;
       }
       return result;
    }
}

char OperatorJudgement(char optr1,char optr2)
{
    if(optr1=='+' || optr1=='-')
    {
       if(optr2=='+' || optr2=='-' || optr2==')' || optr2=='#')
           return '>';
       if(optr2=='*' || optr2=='/' || optr2=='%' || optr2=='(')
           return '<';
    }  
    if(optr1=='*' || optr1=='/' || optr1=='%')
    {
       if(optr2=='+' || optr2=='-' || optr2=='*' || optr2=='/' || optr2=='%' || optr2==')' || optr2=='#')
           return '>';
       if(optr2=='(')
           return '<';
    }
    if(optr1=='(')
    {
       if(optr2==')')
           return '=';
       if(optr2=='#')
           return 'E';
       if(optr2=='+' || optr2=='-' || optr2=='*' || optr2=='/' || optr2=='%' || optr2=='(')
           return '<';
    }
    if(optr1==')')
    {
       if(optr2=='(')
           return 'E';
       else
           return '>';
    }
    if(optr1=='#')
    {
       if(optr2==')')
           return 'E';
       if(optr2=='#')
           return '=';
       else
           return '<';
    }
}

bool IsLegalMod(double opnd1,double opnd2)
{
    if(opnd1-(int)opnd1!=0.0 || opnd2-(int)opnd2!=0.0 || opnd2==0.0)
       return false;
    return true;
}

double Calculate(double opnd1,char optr,double opnd2)
{
    if(optr=='+')
       return opnd1+opnd2;
    if(optr=='-')
       return opnd1-opnd2;
    if(optr=='*')
       return opnd1*opnd2;
    if(optr=='/')
       return opnd1/opnd2;
    if(optr=='%')
       return (double)((int)opnd1%(int)opnd2);
}

int main()
{
    int i,j;
    bool isLegalInfixNonation;
    char s[L],t[L];

    while(gets(s))
    {
       isLegalInfixNonation=true;
       for(i=0;s[i]!='\0';i++)
       {
           if(IsLegalChar(s[i])==false)
           {
              isLegalInfixNonation=false;
              break;
           }
       }
       strcat(s,"#");
       while(OPND.empty()==false)
           OPND.pop();
       while(OPTR.empty()==false)
           OPTR.pop();

       i=0;
       OPTR.push('#');
       while((s[i]!='#' || OPTR.top()!='#') && isLegalInfixNonation==true)
       {
           if(isdigit(s[i]) || s[i]=='.')
           {
              int point=0,count=0;
              for(j=0;isdigit(s[i]) || s[i]=='.';i++,j++)
              {
                  t[j]=s[i];
                  if(s[i]=='.')
                     count++,point=j;
              }
              double opnd=ToOperand(t,j,count,point);
              if(opnd==-1.0)
              {
                  isLegalInfixNonation=false;
                  break;
              }
              else
              {
                  OPND.push(opnd);
              }
           }
           else
           {
              char optr1=OPTR.top(),optr2=s[i];
              char judgement=OperatorJudgement(optr1,optr2);
              if(judgement=='E')
                  isLegalInfixNonation=false;
              else
              {
                  if(judgement=='<')
                  {
                     OPTR.push(optr2);
                     i++;
                  }
                  else if(judgement=='=')
                  {
                     OPTR.pop();
                     i++;
                  }
                  else if(judgement=='>')
                  {
                     OPTR.pop();
                     if(OPND.empty()==true)
                     {
                         isLegalInfixNonation=false;
                         break;
                     }
                     double opnd2=OPND.top();
                     OPND.pop();
                     if(OPND.empty()==true)
                     {
                         isLegalInfixNonation=false;
                         break;
                     }
                     double opnd1=OPND.top();
                     OPND.pop();
                     if(optr1=='%')
                     {
                         if(IsLegalMod(opnd1,opnd2)==false)
                         {
                            isLegalInfixNonation=false;
                            break;
                         }
                     }
                     if(optr1=='/')
                     {
                         if(opnd2==0.0)
                         {
                            isLegalInfixNonation=false;
                            break;
                         }
                     }
                     double result=Calculate(opnd1,optr1,opnd2);
                      OPND.push(result);
                  }
              }
           }
       }
       if(isLegalInfixNonation==false)
           puts("ERROR IN INFIX NOTATION");
       else
       {
           if(OPND.size()!=1)
              puts("ERROR IN INFIX NOTATION");
           else
              printf("%.2lf\n",OPND.top());
       }
    }
    return 0;
}

 


,
  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。