unary minus in shunting yard expression parser

Question

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 #include #include #include #include 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))…

Accepted Answer

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.

unary minus in shunting yard expression parser

Solution

Problem

Related problems