调车场表达式解析器中的一元减号 [英] unary minus in shunting yard expression parser
问题描述
这是我使用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.
这篇关于调车场表达式解析器中的一元减号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
