унарный минус в маневровом синтаксическом анализаторе
вот мой синтаксический анализатор выражений, использующий алгоритм маневрового двора
это работает хорошо, как и ожидалось, за исключением одной ситуации, когда я использую унарный минус, как в -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;
}
Решение
Вышеуказанная опция верна, но она будет очень громоздкой и глючной.
Рассмотрим случай 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 ^ 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 перед первым символом «-». Вы должны сделать это также, когда после — (.
Более хорошие реализуют либо унарный оператор минус, либо рассматривают его как часть числового литерала.