Konvertieren von einem infix-Ausdruck zu postfix (C++) - Verwendung von Stacks
Mein Dozent gab mir eine Zuweisung zu erstellen, ein Programm zum konvertieren von und in infix-Ausdruck postfix Stapel verwenden. Ich habe die stack-Klassen und einige Funktionen zum Lesen der infix-Ausdruck.
Aber diese Funktion, genannt convertToPostfix(char * const inFix, char * const postFix)
die dafür verantwortlich ist, zu konvertieren, der inFix-Ausdruck in der array-inFix dem post-fix-expression in den array postFix-Stapel verwenden, ist nicht dabei, was es wohl zu tun. Könnt Ihr mir helfen und mir sagen was ich falsch mache?
Den folgenden code, wo die Funktionen zur Konvertierung von inFix zu postFix und convertToPostfix(char * const inFix, char * const postFix)
ist was ich brauche Hilfe Befestigung:
void ArithmeticExpression::inputAndConvertToPostfix()
{
char inputChar; //declaring inputChar
int i = 0; //inizalize i to 0
cout << "Enter the Arithmetic Expression(No Spaces): ";
while( ( inputChar = static_cast<char>( cin.get() ) ) != '\n' )
{
if (i >= MAXSIZE) break; //exits program if i is greater than or equal to 100
if(isdigit(inputChar) || isOperator(inputChar))
{
inFix[i] = inputChar; //copies each char to inFix array
cout << inFix[i] << endl;
}
else
cout << "You entered an invalid Arithmetic Expression\n\n" ;
}
//increment i;
i++;
convertToPostfix(inFix, postFix);
}
bool ArithmeticExpression::isOperator(char currentChar)
{
if(currentChar == '+')
return true;
else if(currentChar == '-')
return true;
else if(currentChar == '*')
return true;
else if(currentChar == '/')
return true;
else if(currentChar == '^')
return true;
else if(currentChar == '%')
return true;
else
return false;
}
bool ArithmeticExpression::precedence(char operator1, char operator2)
{
if ( operator1 == '^' )
return true;
else if ( operator2 == '^' )
return false;
else if ( operator1 == '*' || operator1 == '/' )
return true;
else if ( operator1 == '+' || operator1 == '-' )
if ( operator2 == '*' || operator2 == '/' )
return false;
else
return true;
return false;
}
void ArithmeticExpression::convertToPostfix(char * const inFix, char * const postFix)
{
Stack2<char> stack;
const char lp = '(';
stack.push(lp); //Push a left parenthesis ‘(‘ onto the stack.
strcat(inFix,")");//Appends a right parenthesis ‘)’ to the end of infix.
//int i = 0;
int j = 0;
if(!stack.isEmpty())
{
for(int i = 0;i < 100;){
if(isdigit(inFix[i]))
{
postFix[j] = inFix[i];
cout << "This is Post Fix for the first If: " << postFix[j] << endl;
i++;
j++;
}
if(inFix[i] == '(')
{
stack.push(inFix[i]);
cout << "The InFix was a (" << endl;
i++;
//j++;
}
if(isOperator(inFix[i]))
{
char operator1 = inFix[i];
cout << "CUrrent inFix is a operator" << endl;
if(isOperator(stack.getTopPtr()->getData()))
{
cout << "The stack top ptr is a operator1" << endl;
char operator2 = stack.getTopPtr()->getData();
if(precedence(operator1,operator2))
{
//if(isOperator(stack.getTopPtr()->getData())){
cout << "The stack top ptr is a operato2" << endl;
postFix[j] = stack.pop();
cout << "this is post fix " << postFix[j] << endl;
i++;
j++;
//}
}
}
else
stack.push(inFix[i]);
//cout << "Top Ptr is a: "<< stack.getTopPtr()->getData() << endl;
}
for(int r = 0;r != '\0';r++)
cout << postFix[r] << " ";
if(inFix[i] == ')')
{
while(stack.stackTop()!= '(')
{
postFix[j] = stack.pop();
i++;
j++;
}
stack.pop();
}
}
}
}
Hinweis: die Funktion convertToPostfix wurde mit Hilfe dieses Algorithmus:
- Drücken Sie eine linke Klammer ‘(‘ auf den stack.
- Fügen Sie eine Rechte Klammer ')' am Ende von infix.
-
Während der stack nicht leer ist, Lesen Sie infix von Links nach rechts und führen Sie die folgenden:
- Wenn das aktuelle Zeichen in infix ist eine Ziffer, kopieren Sie es auf das nächste element von postfix.
- Wenn das aktuelle Zeichen in infix ist eine Klammer, schieben Sie es auf den Stapel.
-
Wenn das aktuelle Zeichen in infix ein operator ist,
- Pop-operator(s) (falls vorhanden) an der Spitze des Stapels, während Sie die gleiche oder eine höhere Priorität als der aktuelle Betreiber, und legen Sie die geknallt Betreiber in postfix.
- Push-das aktuelle Zeichen in infix auf dem Stapel.
- Wenn das aktuelle Zeichen in infix eine Rechte Klammer
- Pop-Operatoren aus der Spitze des Stapels und legen Sie Sie in postfix, bis eine linke Klammer oben auf dem Stapel.
- Pop (und verwerfen) die linke Klammer vom stack.
- Es sei denn, du hast masochistische Gefühl, Sie Googeln für "rekursiver Abstieg" oder (vor allem) "Rangier-yard-Algorithmus" wird wohl eher hilfreich (wenn Sie bereits versuchen, verwenden Sie eine der folgenden, entschuldige ich mich-zumindest auf den ersten Blick habe ich nicht erkennen es als deren Umsetzung).
- Ich folgte der Algorithmus, den ich eben editiert in meinem post war da von meinem Dozenten, aber ich weiß nicht scheinen, damit es funktioniert.
- Sie sollte ein team mit mit dieser person. Er stellte die gleiche Frage zur gleichen Zeit, die Sie haben.
- Wir sind in der gleichen Klasse, aber unterschiedliche Gruppe.
- So, Schritt durch diesen code im debugger, was bedeutet es Ihnen sagen? Erzähl mir nicht, du weißt nicht, was ein debugger ist, oder wie Sie es verwenden, oder dass Sie noch nicht versucht, es zu benutzen, oder versucht, aber hilflos gescheitert. C ' Mon. Man kann es nicht mit dem Gehirn allein, das tool zu verwenden.
- ich habe. Code stürzt jetzt. Ich bearbeitet den code in der post.
- Seine Klasse ist vorbei, es ist eine einfache übung, es ist eine Verschwendung von Mühe.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dies ist im Grunde ein Kommentar zur Antwort von Yuushi.
precedence(rightOp, leftOp)
). Dann sollten Sie dokumentieren, was das Ergebnis bedeutet - jetzt gibt true zurück, wenna rOp b lOp c == (a rOp b) lOp c
(ja, die Betreiber, um nicht mit dem übereinstimmt, was Sie es nennen - "+" und "-" sind nicht das gleiche in beiden Aufträge zum Beispiel).a - b * c
Ausgabea b c
und der stack ist[- *]
. nun Lesen Sie ein+
, und Sie brauchen, um pop-die beiden Betreiber, was ina b c * -
. I. e., der Einganga - b * c + d
führen solltea b c * - d +
Update: angehängt komplette Lösung (basierend auf Yuushi Antwort):
while (true)
precedence
Funktiona ^ b + c == ( a ^ b ) + c
. Die Rangfolge der+
Betreiber ist höher als^
. Sollte nichta ^ b + c == a ^ ( b + c )
?+
hat eine höhere Priorität als^
.So gibt es eine Reihe von Problemen mit Ihrem code. Poste ich was (sollte) eine korrigierte Lösung, die reichlichen Kommentare zu erklären, was passiert ist und wo Sie Fehler gemacht habe. Ein paar Dinge vorne Weg:
Verwende ich
std::string
stattchar *
denn es macht die Dinge viel sauberer, und ehrlich gesagt, sollten Sie es inC++
es sei denn, Sie haben einen sehr guten Grund, nicht zu (wie die Interoperabilität mit einemC
Bibliothek). Diese version gibt auch einestring
stattchar *
als parameter.Bin ich mit dem stack aus der standard-Bibliothek
<stack>
, die ist etwas anders zu Ihr nach Hause gerollt ein.top()
zeigt das nächste element ohne entfernen Sie es aus dem Stapel, und diepop()
zurückvoid
, aber entfernt das oberste element vom stack.Es ist eine Kostenlose Funktion, die nicht Teil einer Klasse, aber das sollte leicht zu ändern - es ist einfach leichter für mich zu testen, auf diese Weise.
Ich bin nicht davon überzeugt, Ihre Rangfolge-Tabellen korrekt sind, aber ich lasse Sie überprüfen.
Hier ist meins mit C mit mehreren Ziffern Auswertung.
C++ - Implementierung ist nachfolgend angegeben:
Rangfolge ist das problem in diesem Fall. Die richtige Rangfolge in absteigender Reihenfolge ist:
In der obigen Frage betrachten Sie die Vorrang-Funktion
für jeden Wert in operator1 entsprechenden Wert von operator2 sollte geprüft werden, ob die Rangfolge nach RANGFOLGE der TABELLE oben erwähnt. Keine Rückgabe von jedem Wert ohne die richtige Vergleich.