8588 表达式求值

时间限制:1000MS 内存限制:1000K

提交次数:182 通过次数:84

题型: 编程题语言: 无限制

Description

利用栈编写表达式求值程序：输入含有“+”、“-”、“*”、“/”四则运算的表达式，其中负数要用（0-正数）表示，并以=结束。要求输出表达式的值（两运算符号的优先关系见教材表3.1）。此题目可选做。

Input

第一行：一个算术表达式

Output

第一行：算术表达式的值

Sample Input

3*(9-7)=

Sample Output

Provider

yqm

1 #include
     
        2 #include
      
         3 #include
       
          4 #define SElemType char  5 #define SIntType int    6 #define STACK_INIT_SIZE 100  7 #define STACKINCREMENT 10  8 #define Status int  9 #define OK 1 10 #define ERROR 0 11 #define Dif -1 12  13 char s[10000]; 14  15 typedef struct{ 16     SElemType *base; 17     SElemType *top; 18     int stacksize; 19 }Spstack; 20  21 typedef struct{ 22     SIntType *base; 23     SIntType *top; 24     int stacksize; 25 }SIstack; 26  27 Status InitStack(Spstack &S) 28 {
   //创建存储运算符的栈队列  29     S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); 30     if(!S.base) return ERROR; 31     S.top = S.base; 32     S.stacksize = STACK_INIT_SIZE; 33     return OK; 34 } 35 Status InitStack_int(SIstack &S) 36 {
   //创建存储数值的栈队列  37     S.base = (SIntType*)malloc(STACK_INIT_SIZE * sizeof(SIntType)); 38     if(!S.base) return ERROR; 39     S.top = S.base; 40     S.stacksize = STACK_INIT_SIZE; 41     return OK; 42 } 43 Status InsertStack(Spstack &S, SElemType e) 44 { 45     SElemType *newbase; 46     SElemType *Point; 47     int flag = 0; 48     if(S.top - S.base >= S.stacksize) 49     { 50         newbase = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType)); 51         if(!newbase) return ERROR; 52         S.base = newbase;  53         S.top = S.stacksize + S.base; 54         S.stacksize += STACKINCREMENT; 55          56     } 57     *S.top++ = e; 58     return OK; 59 } 60 Status InsertStack_int(SIstack &S, SIntType e) 61 { 62     SIntType *newbase; 63     SIntType *Point; 64     int flag = 0; 65     if(S.top - S.base >= S.stacksize) 66     { 67         newbase = (SIntType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SIntType)); 68         if(!newbase) return ERROR; 69         S.base = newbase; 70         S.top = S.stacksize + S.base; 71         S.stacksize += STACK_INIT_SIZE; 72                  73     } 74     *S.top++ = e; 75     return OK; 76 } 77  78 Status PrecedeStack(SElemType optr, SElemType c) 79 {
   // 运算符优先顺序  80     switch(optr) 81     { 82         case '+':  83         case '-': switch(c) 84         { 85             case '+': 86             case '-':   87             case ')': 88             case '=':return Dif; 89             case '(': 90             case '*': 91             case '/': return OK;  92         } 93          94         case '*': 95         case '/': switch(c) 96         { 97             case '+': 98             case '-': 99             case '*':100             case '/':101             case '=':102             case ')': return Dif;103             case '(': return OK;104         }105         case '(':switch(c)106         {107             case '+':108             case '-': 109             case '*':110             case '/':111             case '(': return OK;112             case ')': return ERROR;113         }114         case ')':switch(c)115         {116             case '+':117             case '-': 118             case '*':119             case '/': 120             case '(': 121             case ')':122             case '=': return Dif;123         }124         case '=':switch(c)125         {126             case '+':127             case '-': 128             case '*':129             case '/': 130             case '(': 131             case ')':132             case '=': return Dif;133         }134         135     }    136 }137 138 SElemType GetTopStack(Spstack S)139 {140     if(S.top == S.base) return ERROR;141     return *(S.top-1);142 }143 144 Status LoadStack_int(SIstack T)145 {146     SIntType *Point1 = T.base;147     if(Point1 == T.top) return ERROR;148     while(Point1 != T. top)149     {150        printf("%d", *Point1++);151     }152     printf("\n");153     return  OK;154 }155 Status EmptyStack(Spstack &T)156 {157     158     if(T.top == T.base) return ERROR;159     if(T.base)160     free(T.base);161     return OK;162 }163 164 Status EmptyStack_int(SIstack &T)165 {
   //释放栈 166     167     if(T.top == T.base) return ERROR;168     if(T.base)169     free(T.base);170     return OK;171 }172 173 int RunOpera(SIntType a, SElemType run, SIntType b )174 {175     switch(run)176     {177         case '*': return a*b;178         case '/': return b/a;179         case '-': return b-a;180         case '+': return a+b;181     }    182 183 }184 185 int main()186 {187     Spstack OPTR;188     SIstack OPND;189     SElemType x, e, ch;190     int n, i, count = 0,countit = 0,  sum = 0, flag = 0,  k = 0, result = 0, dig = 0;191     InitStack(OPTR);192     InitStack_int(OPND);193     memset(s, 100, sizeof(s));194     fgets(s, 100, stdin);195     ch = s[sum++];196     while(!(OPTR.top == OPTR.base && ch == '='))197     {198     if(!(('0' <= ch &&ch <= '9'))) 199     {200         countit = 0; 201     }202     if('0' <= ch && ch <= '9') 203     {204         if(countit++ != 0) 205         {206             dig = ch - '0';207             *(OPND.top-1) = (*(OPND.top-1)*10) + dig;208         }209         else  InsertStack_int(OPND, (ch - '0'));210     }211     else if(count == 0)  212     {213         InsertStack(OPTR, ch);  count =1;214     }215     else  switch(PrecedeStack(GetTopStack(OPTR), ch))216     {217             case OK:    218             case ERROR:  InsertStack(OPTR, ch); break;              219             case Dif: if(*(OPTR.top - 1) == ')') 220                       {221                           OPTR.top = OPTR.top - 2;222                           if(OPTR.top == OPTR.base) count = 0;223                              flag = 1;224                             break;225                       }226                       227                     result = RunOpera(*(OPND.top - 1), *(OPTR.top - 1), *(OPND.top - 2) );  228                     OPND.top = OPND.top - 2;229                     *(OPND.top++) = result;230                      OPTR.top--;231                       if((ch == ')' && *(OPTR.top-1) == '(') || (OPTR.top == OPTR.base && ch != '=')) 232                       *OPTR.top++ = ch;233                     else flag = 1;  234                     break;       235                 236         }237 238          if(flag)239          {240              flag = 0;241              continue;242          }243          else ch = s[sum++];     244     }245     LoadStack_int(OPND);246     EmptyStack_int(OPND);247     EmptyStack(OPTR);248     return 0;249 }

结题报告：

我忘了我是在什么时候开始做这题的，LRE了很多次WA了很多次，删删减减了很多很多的代码，有时间停下了来的时候总是还想着这题没有完成

离ＡＣ还很远呢，有时对着它无可奈何，不知所措，但还是坚持了下来，我一直想着我能够努力地让它ＡＣ过去，师兄说这百度一下哪里都有，

我说我舍不得，他帮我测试了几组数据，终于发现还是出了问题，很快我找到了BUG，加多了一行代码，断网前来的一分钟我提交，AC了。

问题出现的原因：

1.以前拖拖拉拉，连续遇到WA总觉得有点晦气，不知不觉就拖了很长的一段时间，每次翻看代码消耗了较多时间；

2.LRE是因为在释放栈队列的时候出现了问题，我申请空间的时候是一块一块申请的，而释放的时候是一个节点释放，这里出现了问题

OJ的错误提示：

3.WA是因为没有考虑全面，测试数据不够多，浮躁地以为自己的程序没有错误，其实这感觉是因为自己找不出哪里出现错误

转载于:https://www.cnblogs.com/liaoguifa/archive/2012/09/24/2699480.html

你可能感兴趣的文章