调车场表达式解析器中的一元减号

本文介绍了调车场表达式解析器中的一元减号的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这是我使用Shunting-yard算法的表达式解析器它可以正常工作，除非在一种情况下，当我在-2 * 3中使用一元负值时它不会工作(我认为应该不行，因为我没有在算法中找到任何东西来处理这个问题).有一种简单的方法可以解决此问题吗?(这是一个简单的解析器，我只需要()+-*/^)问候踏板车

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; }

推荐答案

上面的选项是正确的，但它会变得非常麻烦和麻烦.考虑情况 2 *-(1 + 2)^-(2 + 5 *-(2 + 4)).如您所见，您需要考虑很多事情.同样，例如，每当您找到"*-("时，您就会知道将其替换为*(0-(....，这将在繁琐的递归函数中进行编码.最好的解决方案要容易得多.在运算符上，请考虑以下情况:该运算符为-"并且在另一个运算符之前，或者在左括号之前，或者它是输入的第一个字符(这些情况意味着它是一元的减号而不是二进制数).在这种情况下，您将其更改为另一个字符，说"u"(这是我的情况)，并使其优先级与"^"相同.

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. At the operators, take in 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 '^'.

此外，将其视为数字文字的一部分也有其难处.想象一个情况，例如-2 ^ 4.在Wolfram Alpha中，您将获得-16，而不是16.

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

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

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.