унарный минус в анализаторе выражения маневровой станции

вот мой синтаксический анализатор выражений, использующий алгоритм сортировочной станции, он работает хорошо, как и ожидалось, за исключением одной ситуации, когда я использую унарный минус, как в -2 * 3, он не будет работать (я думаю, что не должен, потому что я ничего не нашел в алгоритме чтобы справиться с этим) есть ли простой способ исправить это? (это простой синтаксический анализатор, который мне нужен только () + - * / ^) С уважением, Педрам

#include <cctype>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
int olaviat (char c) {
   /*************
    **Operator precedence 
    *************/
  switch(c) {
       case '-' : case '+' :
           return 1 ;
       case '*' : case '/' :
           return 2 ;
       case '^' :
           return 3 ;
       default :
           return 0 ;
  }
}
double eval(char *exp) {
    /*************
    **Convert to reverse polish
    *************/
    char n [50] , o[50] ;
    static int nl = 0  , ol = 0 ;

    while (*exp) {
            while(isspace(*exp)) *exp++ ;
        if(*exp == '(') {
             o[ol++]  = *exp++ ;
           }
        else if (*exp == ')'){
            while(o[--ol]!='('){
                    n[nl++] = o[ol];
                    n[nl++] = ' ';
                  }
                  *exp++;
        }
        else if (isdigit(*exp)) {
          while (isdigit(*exp)) {
            n[nl++] = *exp++ ;
          }
        n[nl++] = ' ' ;
        }
        else if (strchr("+-*/^",*exp)){
            if(olaviat(*exp) > olaviat(o[ol-1])) {
               o[ol++]  = *exp++ ;


            }
            else {
                    if(olaviat(*exp) == olaviat(o[ol-1]) && olaviat(*exp)== 3) {
                      o[ol++]  = *exp++ ;
                    }else{
                n[nl++] = o[ol-1] ;
                n[nl++] = ' ' ;
                o[--ol] = '\0' ;

                    }
            }
        }

    }

for (int k = ol-1 ; k >= 0 ; k --){
    n[nl++] = o[k];
    n[nl++] = ' ' ;
}
/*******************************/
cout << "Reverse Polish" << endl ;
for (int i = 0 ; i < nl-1 ; i++){
        cout << n[i]  ;
    }
cout << endl ;
//n[nl+1] = '\0' ;
/*******************************
**Calculate Result
*******************************/
    double temp[50];
    char *e ;
    ol = 0;
   int  nol = 0 ;
    e=n ;
    int digitcount = 0;
    while (*e) {
            while (isspace(*e)) *e++;
        if (isdigit(*e)) {
          while (isdigit(*e)) {
             o[ol++] =*e++ ;
             digitcount++ ;
          }
        temp[nol++] = atof(o) ;
        for (int i = 0 ; i < digitcount ; i++)
            o[i]='\0' ;
        ol=0;
        digitcount = 0 ;
        }
        else if (strchr("+-*/^",*e)){
          // char opr ;
           double tempAns = 0;
           switch (*e) {
              case '+' :
                  tempAns = temp[nol-2] + temp [nol-1] ;
                  break ;
              case '-' :
                  tempAns = temp [nol-2] - temp [nol-1] ;
                  break;
              case '*' :
                  tempAns = temp [nol-2] * temp [nol-1] ;
                  break;
              case '/' :
                  tempAns = temp[nol-2] / temp[nol-1];
                  break ;
              case '^' :
                  tempAns = pow(temp[nol-2],temp [nol-1]);
                  break ;
              default :
                cout << "\n Unknown error" ;
                continue;
           }
           *e++ ;
           nol--;
           temp[nol-1] = tempAns ;
           temp[nol] = NULL ;
        }
        else {
            break ;
        }
    }
    double ans = temp[0];

  return ans ;
}

int main() {

char exp[100];
char c;
start :
    cin.get (exp , 99);
    cout << "\n\tANS= " << eval(exp)  ;
    cout << endl ;
    system("PAUSE");
    return 0;
} 

person PedramH    schedule 07.05.2013    source источник
comment
Хотя это был другой вопрос, я изложил решение в своем ответе на stackoverflow.com/questions/16380234/   -  person rici    schedule 07.05.2013


Ответы (2)


Приведенный выше вариант правильный, но он будет очень громоздким и глючным. Рассмотрим случай 2*-(1+2)^-(2+5*-(2+4)). Как видите, нужно учитывать многие вещи. Кроме того, всякий раз, когда вы встречаете, например, "*-(", вы знаете, что замените это на *(0-(....), что будет закодировано в громоздкой рекурсивной функции. Лучшее решение намного проще. В операторах , примите во внимание случаи, когда оператор "-" предшествует другому оператору или предшествует левой скобке, или когда это первый символ ввода (эти случаи означают, что это унарный минус, а не В этом случае вы меняете его на другой символ, скажем, «u» (это было в моем случае), и делаете его приоритет таким же, как у «^».

Кроме того, обработка его как части числового литерала имеет свою загвоздку. Представьте себе такой случай, как -2 ^ 4. В Wolfram Alpha вы получите -16, а не 16.

И рассмотрите возможность использования стеков. Они сделают вашу жизнь проще.

Позвольте мне объяснить, что я имел в виду. Предположим, вам дан ввод:

2 / - 7 + ( - 9 * 8 ) * 2 ^ - 9 - 5

Сделав замены, которые я предложил, он стал бы таким:

2 / u 7 + ( u 9 * 8 ) * 2 ^ u 9 - 5

Теперь ваш переключатель приоритета оператора должен быть изменен на:

switch(c)
{
       case '-' : case '+' :
           return 1 ;
       case '*' : case '/' :
           return 2 ;
       case '^' : case 'u': //note the 'u' operator we added
           return 3 ;
       default :
           return 0 ;
}

И, конечно, нужно внести изменения для поддержки этого унарного оператора.

person TGO    schedule 16.06.2013
comment
Большое спасибо. Я хотел бы добавить, что при проверке предшествующего оператора убедитесь, что этот оператор не является унарным отрицанием. Это предотвращает превращение -1 - 4 в -1 -4 и появление ошибок. Это также останавливает работу ---4 (что является разумным поведением, потому что ---4 не является правильным математическим синтаксисом. -(-(-4)) все равно будет работать). - person ; 27.10.2016

Один из вариантов — поставить 0 впереди, если первый символ — «-». Вы должны сделать это также, когда - находится после (.

Более хорошие реализуют либо унарный оператор минус, либо рассматривают его как часть числового литерала.

person jmihalicza    schedule 07.05.2013
comment
+1, вам также придется искать унарные - и + в другом месте выражения, например. "1-(-2)" или "1*-2". Bracer использует поиск/замену для исправить эту проблему. - person user7116; 07.05.2013