here is my expression parser using shunting-yard algorithm it work well as expected except in one situation , when I use unary minus like in -2*3 it wont work (I think it shouldn't because I didn't find anything in algorithm to handle this ) is there a simple way that I can fix this? (this is a simple parser I only need () + - * / ^ ) Regards 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;
}
The above option is correct, but it would get very cumbersome and buggy.
Consider the case 2*-(1+2)^-(2+5*-(2+4)).
As you can see you need to take in account many things. Also whenever you find *-(, for example, you know that you'll substitute that with *(0-(..., which would be coded in a cumbersome recursive function.
The best solution is much easier. When parsing the operators, take into account the cases when the operator is - and it is preceded by another operator, or preceded by a left parenthesis, or when it is the first character of the input (these cases mean that it is a unary minus rather than binary). In this case, you change it to another character, say u (this was my case), and make its precedence the same as that of ^.
Also, treating it as part of the number literal has its catch. Imagine a case such as -2^4. In Wolfram Alpha you'd get -16, not 16.
And consider using stacks. They'll make your life easier.
Let me explain what I meant. Consider you are given the input:
2 / - 7 + ( - 9 * 8 ) * 2 ^ - 9 - 5
Making the replacements I suggested, it would become like this:
2 / u 7 + ( u 9 * 8 ) * 2 ^ u 9 - 5
Now your operator precedence switch should be changed to:
switch(c)
{
case '-' : case '+' :
return 1 ;
case '*' : case '/' :
return 2 ;
case '^' : case 'u': //note the 'u' operator we added
return 3 ;
default :
return 0 ;
}
And, of course, you need to make changes to support this unary operator.