题目1101：计算表达式九度OJ

た入场券 2021-11-02 14:20 173阅读 0赞

算法：

1.1个栈寄存运算符，1个栈寄存操作数

2.优先级用数组保存好

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    #include<vector>
    #include<string>
    #include<math.h>
    #include<map>
    #include<set>
    #include<stack>
    #include<algorithm>
    using namespace std;
    stack<int>OpE;//操作数栈 
    stack<char>OpR;//运算符栈 
    //算符间优先级 
    int Opet[100];
    //栈顶优先权 
    int Pri[8][8] = {
         {
         1,1,-1,-1,-1,1,1},
                     {
          1,1,-1,-1,-1,1,1},
                     {
          1,1,1,1,-1,1,1},
                     {
          1,1,1,1,-1,1,1},
                     {
          -1,-1,-1,-1,-1,0,0},
                     {
          1,1,1,1,1,1,1},
                     {
          -1,-1,-1,-1,-1,-1,-2}
                    };
    void init( )
    {
      memset(Opet,0,sizeof(Opet));
      Opet['+'] = 0,Opet['-'] = 1,Opet['*'] = 2;
      Opet['/'] = 3,Opet['('] = 4, Opet[')'] = 5;
      Opet['#'] = 6;    
    }
    //判断优先级 
    int jugde( char p, char q)
    {
       return Pri[Opet[p]][Opet[q]];    
    }
    
    int solve(char *str )
    {
      int len = strlen(str), x, y, i = 0, j;
      char Op = 0, temp[1100];
      init( );
      OpR.push('#');
      bool f = true;
      str[len] = '#';
      while( i <= len && f)
      {
         if( str[i] >= '0' && str[i] <= '9' ) //操作数直接入栈 
         {  
              int ans = 0;
              for(j = i; j < len; j++)
                 if( str[j] >= '0' && str[j] <= '9' )
                   temp[ans++] = str[j];
                 else
                   break;
              i = j;
              temp[ans] = '\0';
              OpE.push(atoi(temp));
         }
         else
         {  
            switch( jugde(OpR.top(),str[i]) )
            {
              case 0: OpR.pop();i++;break; 
              case 1: 
              {
                 Op = OpR.top( );
                 OpR.pop();
                 x = OpE.top();
                 OpE.pop();                 
                 y = OpE.top( );
                 OpE.pop( ); 
                 if( Op == '+' )
                     OpE.push( x + y );
                 else if( Op == '-' )
                     OpE.push( y - x );
                 else if( Op == '*' )
                     OpE.push( y * x );
                 else if( Op == '/' )
                     OpE.push( y / x );
                 break;    
              }
              case -1: OpR.push(str[i]);i++;break;
              case -2: f = false;break;    
            }    
             
         }    
           
      }     
      return OpE.top();
    }
     
    int main( )
    {
       char str[1000];
       while( scanf("%s",str) != EOF )
       {
         printf("%d\n",solve( str ));
       }
       return 0;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/08/21/2648464.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/e33f5c81c4cd4197b8846920aa1a4068.png