So I had to write a program for school that converted from infix too reverse polish notation and I believe it works but am not sure. Can anyone please provide sample test data and answers so I can test it. If it does work ill go ahead and post the source to it.
Edit: Forgot to mention it only allows for parentheses and constants.
I presume you're using Dijkstra's shunting yard algorithm?
Simple:
3+4
3 4 +
(1+2)*3
3 2 1 + *
Moderate:
5 + ((1 + 2) * 4) − 3
5 1 2 + 4 * 3 - +
(1+2)/10
1 2 + 10 /
I ran all of the test data you gave me and it works. Thanks for those. And here is the code for it, not sure if it was the best way to do it, but it works.
Code:
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
bool is_opening_brace(char input)
{
if(input == '(')
return true;
else
return false;
}
bool is_operand(char input)
{
if(input == '+' || input == '-' || input == '/')
return false;
else if(input == '*' || input == '(' || input == ')')
return false;
else
return true;
}
bool is_closing_brace(char input)
{
if(input == ')')
return true;
else
return false;
}
int main(int argc, char** argv)
{
string infix_input;
char token;
char popped;
stack<char> operation;
queue<char> rpn_equation;
cout << "Please enter an expression: ";
cin >> infix_input;
for(int i = 0; i < infix_input.length();i++) {
token = infix_input.at(i);
if(is_operand(token))
rpn_equation.push(token);
else if (is_opening_brace(token))
operation.push(token);
else if(is_closing_brace(token)) {
popped = operation.top();
operation.pop();
while(popped != '(') {
rpn_equation.push(popped);
popped = operation.top();
operation.pop();
}
} else {
if(operation.size() == 0 || (token == '*' || token == '/') && (operation.top() == '+' || operation.top() == '-'))
operation.push(token);
else {
while(operation.size() > 0 && (operation.top() == '*' || operation.top() == '/') && (token == '+' || token == '-')) {
rpn_equation.push(operation.top());
operation.pop();
}
operation.push(token);
}
}
}
while(operation.size() > 0) {
rpn_equation.push(operation.top());
operation.pop();
}
while(rpn_equation.size() > 0){
cout << rpn_equation.front();
rpn_equation.pop();
}
cout << endl;
}
A couple of issues I found:
1. I would convert this infix expression:
Code: 5 + ((1 + 2) * 4) - 3
to this postfix expression:
Code: 5 1 2 + 4 * + 3 -
in order to maintain the left-to-right evaluation for operators of equal precedence (+ and -)
2. The code doesn't print spaces between operands:
Code: Please enter an expression: 5+((1+2)*4)-3
512+4*3-+
If I put spaces in the expression I get something totally wrong:
Code: Please enter an expression: 5 + ((1 + 2) * 4) - 3
5
Other than those little issues, it does convert infix to RPN well.
Yeah we where told to assume there would be no spaces in the input. And the printing a space would be trivial to add, I just didn't bother to do it.
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.
»
Go to Registration page
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
