2013-05-07 9 views
7

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

#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; 
} 
+0

Хотя это был другой вопрос, я изложил решение в своем ответе на http://stackoverflow.com/questions/16380234/handling-extra-operators-in-shunting-yard/16392115#16392115 – rici

ответ

6

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

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

И подумайте об использовании стеков. Они облегчат вашу жизнь.

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

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

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

2/и 7 + (и 9 * 8) * 2^и 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 ; 
} 

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

+0

Отлично, спасибо. Я хотел бы добавить, что при проверке предыдущего оператора убедитесь, что оператор не является унарным. Это предотвращает -1 -4 от -1 -4 и создает ошибки. Он также останавливается --- 4 от работы (что является разумным поведением, потому что --- 4 - не правильный математический синтаксис. - (- (- 4)) все равно будет работать). – 2016-10-27 16:29:00

1

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

Nicer те реализуют либо унарный оператор минус или рассматривать его как часть номера буквального

+0

+1, вы 'также придется искать унарные '-' и' + ', закопанные в другом месте выражения, например '" 1 - (- 2) "или' "1 * -2" '. [Bracer использует поиск/замену, чтобы исправить эту проблему] (https://github.com/dtitov/bracer/blob/master/src/main/java/com/autsia/bracer/BracerParser.java). – user7116

+0

Я имею в виду унарный минус везде не только первый символ, как 2 * -5 2^-1, .... – PedramH