I'm trying to write an infix to postfix expression converter using a stack. Basically, it's an implementation of the Shunting Yard algorithm as found on wikipedia.
/*
This function returns the precedence of a presented token. To keep comparisons
simple, the higher the return value, the higher the precedence. Not to be
confused with priority.
From https://web.archive.org/web/20120822075917/http://en.literateprograms.org:80/Special:DownloadCode/Shunting_yard_algorithm_(Python)
*/
int precedence(string token)
{
switch(token.at(0))
{
case '+':
return 1;
case '-':
return 1;
case '*':
return 2;
case '/':
return 2;
case '(':
return 0;
case ')':
return 0;
}
return 0;
}
/*
Returns true if the supplied token is an operator.
*/
bool is_operator(const string& token)
{
return token == "*"
|| token == "/"
|| token == "+"
|| token == "-";
}
/*
Returns true if the supplied token is an operand (not an operator).
*/
bool is_operand(const string& token)
{
return !is_operator(token) && (token != "(") && (token != ")");
}
void display(const vector<string>& v)
{
for(unsigned int i=0; i<v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
string associativity(const string& token)
{
if(token == "*" || token == "+")
{
return "left";
}
else if(token == "/" || token =="-")
{
return "left";
}
return "?";
}
/*
From wikipedia:
while there are tokens to be read:
read a token.
if the token is a number, then push it to the output queue.
if the token is an operator, then:
while (there is an operator at the top of the operator stack with
greater precedence) or (the operator at the top of the operator stack has
equal precedence and
the operator is left associative) and
(the operator at the top of the stack is not a left bracket):
pop operators from the operator stack, onto the output queue.
push the read operator onto the operator stack.
if the token is a left bracket (i.e. "("), then:
push it onto the operator stack.
if the token is a right bracket (i.e. ")"), then:
while the operator at the top of the operator stack is not a left bracket:
pop operators from the operator stack onto the output queue.
pop the left bracket from the stack.
if there are no more tokens to read:
while there are still operator tokens on the stack:
pop the operator onto the output queue.
exit.
*/
vector<string> infix_to_postfix(const vector<string>& infix, bool& error)
{
vector<string> postfix;
stack<string> operators;
for(string token : infix)
{
if(is_operand(token))
{
postfix.push_back(token);
}
if(is_operator(token))
{
while
(
(!operators.empty() && precedence(operators.peek()) > precedence(token))
|| (!operators.empty() && (precedence(operators.peek()) == precedence(token)) && (associativity(token) == "left") && (token != "("))
)
{
string tk = operators.pop();
if(tk != "(" && tk != ")")
{
postfix.push_back(tk);
}
}
operators.push(token);
}
if(token == "(")
{
operators.push(token);
}
if(token == ")")
{
while(!operators.empty() && operators.peek() != "(")
{
postfix.push_back(operators.pop());
}
if(!operators.empty())
{
operators.pop();
}
}
}
while(!operators.empty())
{
postfix.push_back(operators.pop());
}
return postfix;
}
I expect this code to return a valid postfix expression in the form of a vector containing the relevant tokens.
The following evaluate function returns weird numbers for a longer expression I'm testing with.
double evaluate(const vector<string>& postfix, bool& error)
{
error = false;
double result;
stack<double> numbers;
for(unsigned int i=0; i<postfix.size(); i++)
{
string token = postfix[i];
if(is_operand(token))
{
numbers.push(stod(token));
}
else
{
double operand1 = numbers.pop();
double operand2 = numbers.pop();
switch(token.at(0))
{
case '+':
numbers.push(operand1 + operand2);
break;
case '-':
numbers.push(operand1 - operand2);
break;
case '*':
numbers.push(operand1 * operand2);
break;
case '/':
numbers.push(operand1 / operand2);
break;
}
}
}
For example, consider this input and output:
Infix: ( 3 + 3 * 5 ) * 6 - 2 / 1 + 3 + 3 * 5 * ( 4 + 1 )
Postfix: 3 3 5 * + 6 * 2 1 / 3 3 5 4 1 + * * + + -
Result: -29.5
Google says its 184.
Update: I included an associativity function from wikipedia. I also updated the expression result.
Update 2: Incorporated the comments that made this code work.
Obviously your postfix conversion output is already wrong. ( 3 + 3 * 5 ) should have become 3 3 5 * +, not 3 3 + 5 *
while
(
(!operators.empty() && precedence(token) <= precedence(operators.peek()))
|| (!operators.empty() && operators.peek() != "(")
)
This part is wrong. The text says (pred(operators.peek()) > pred(token)) || (pred(operators.peek()) == pred(token) && token != "(").
As a result, you did always wrongly pop the operator whenever it was not a closing parantheses, ignoring operator precedence.
double operand1 = numbers.pop();
double operand2 = numbers.pop();
That part is also wrong. Operand 2 is the one higher on the stack. Switch them around.