I've written a few methods for a calculator. One, which evaluates an entered Postfix expression and another, which transfers an entered infix expression into a postfix expression.
Both these methods allow multi digit integers aswell as floats for the number input types.
Now for my question:
I want to include the negative input in both these methods e.g. Infix: "3 * (-1)".
However I'm kinda lacking an idea on how to implement this problem. Maybe someone can give me ideas or code examples.
I'm including both methods below. A few simple methods are used in them which aren't shown here, but most of the function names should explain them very well. Due to this fact I left them out to keep things as short as possible.
string InfixToPostfix(string expression)
{
string postfix = "";
stack <char> S;
for (int i = 0; i < expression.length(); i++)
{
if (expression[i] == ' ') continue; // Falls leerzeichen oder ',' gefunden mit nächster Iteration weiter machen
else if (IsOperator(expression[i])) // Falls ein Operator gefunden wurde:
{
while (!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(), expression[i])) // Wenn Operator auf Stack höhere Precedence hat, dann diesen an String anhängen und vom Stack nehmen
{
postfix += S.top();
postfix += ' ';
S.pop();
}
S.push(expression[i]); // Wenn Operator die Bedingungen in der while Schleife nicht erfüllt diesen auf Stack legen
}
else if (isDigit(expression[i]) || isComma(expression[i])) //Wenn ein Digit gefunden wurde diesen an String anhängen
{
postfix += expression[i];
if (i+1 >= expression.length() || (!isDigit(expression[i + 1]) && !isComma(expression[i+1]))) //Wenn die nächste Zahl kein Digit ist, dann leerzeichne an String anhängen
{
postfix += ' ';
}
}
else if (expression[i] == '(') // '(' wird auf Stack gepusht
{
S.push(expression[i]);
}
else if (expression[i] == ')') // Wenn ')' gefunden wird, dann:
{
while (!S.empty() && S.top() != '(') // Sofern Stack nicht leer und das oberste Element des Stacks nicht eine Klammer auf ist wird das oberste Element des Stacks dem String angehängt
{
postfix += S.top();
S.pop();
}
S.pop(); //ansonsten wird '(' einfach vom Stack genommen
}
}
while (!S.empty()) // Am Ende der Expression werden alle verbleibenden Elemente vom Stack genommen und Leerzeichen eingefügt
{
postfix += S.top();
postfix += ' ';
S.pop();
}
return postfix; // Rückgabe der jetzt in Postfix vorliegenden Expression
}
//Löst eine Aufgabe in Postfix Notation
float EvaluatePostfix(string expression)
{
stack<float> S;
float j;
for (int i = 0; i< expression.length(); i++) {
if (expression[i] == ' ') continue; // wenn leer oder ',' mit nächster iteration weiter machen
else if (IsOperator(expression[i])) { //Wenn Operator nehme die Operanden vom Stack und wende den Operator an
float operand2 = S.top();
S.pop();
float operand1 = S.top();
S.pop();
float result = PerformOperation(expression[i], operand1, operand2);
S.push(result); //Das Ergebnis zurück auf Stack legen
}
else if (isDigit(expression[i]))
{
float operand = 0;
while (i<expression.length() && isDigit(expression[i]))
{
operand = (operand * 10) + (expression[i] - '0'); //wenn rechts einer Zahl eine weitere Zahl steht, kann operand mal 10 genommen werden und die rechts stehende zahl addiert werden
i++;
}
if (i < expression.length() && isComma(expression[i]))
{
j = 1.0;
i++;
while (i < expression.length() && isDigit(expression[i]))
{
operand = operand + ((expression[i] - '0') / pow(10.0, j));
i++;
j++;
}
}
i--; //Verhindert einen Skip des Operators, i wird sowohl in der while schleife als auch im for hochgezählt
S.push(operand); //Der Operand wird auf den Stack gepusht
}
}
return S.top(); //Stack sollte ein element besitzen, somit ist dies das Ergebnis
}
I don't have a full solution for you, but here are a couple of tips.
I suggest inserting an abstraction layer that reads characters and produces tokens before trying to understand the order of operations. The expression "(42 + 1) - -3" would then become the list { '(', 42, '+', 1, ')', '-', '-', 3 }. A token is often implemented as a class with a type enum (e.g., OPERATOR or NUMBER) and a value (e.g., either a char or a float). (Advanced: You could then convert your tokens into an expression tree, but that might not be necessary here.) This is a little more work, but it makes things much easier to understand than direct string-parsing.
Once you've done that, the key is to determine whether the '-' symbol is intended as infix subtraction or as prefix negation. To do that, look at the previous token (if any). If it's an expression-terminator such as ')' or a number, it's infix subtraction. If there is no such token, or it is some other token, it's prefix negation.