Please help me with this, and make sure the program works, thanks. Write a C++ p
ID: 3890631 • Letter: P
Question
Please help me with this, and make sure the program works, thanks. Write a C++ program that will accept infix expressions (like 5*(4+8)) and convert them to postfix. You are to use Dijkstra's algorithm for converting. Dijkstra's Algorithm: Read in 1 line into a string Print the string while there are characters left to process in the string ----- | get a token (skip over blanks) | if the token is a digit then output(token) | else | ----- | | if the token is '(' then push(token) | | else | | ----- | | | if the token is ')' then | | | ----- | | | | while the top item is not '(' | | | | pop(temp) and output(temp); | | | | pop(temp) | | | ----- | | | else | | | ----- | | | | if the stack is empty then push(token) | | | | else | | | | ----- | | | | | while the stack is not empty | | | | | and the priority (token) <= priority (top item on the stack) | | | | | pop(temp) and output(temp) | | | | | push(token) | | | | ----- | | | ----- | | ---- | ----- ----- while the stack is not empty do pop(temp) and output(temp) Precedence of the Operators: operators : ^ * / + - ( precedence: 3 2 2 1 1 0 where ^ means exponentiation input for the assignment: 2 + 3 * 5 2 + 3 * 5 ^ 6 2 + 3 - 5 + 6 - 4 + 2 - 1 2 + 3 * (5 - 6) - 4 2 * 3 ^ 5 * 6 - 4 (2 + 3) * 6 ^ 2 Output for the assignment 1: 2 + 3 * 5 235*+ 2: 2 + 3 * 5 ^ 6 2356^*+ 3: 2 + 3 - 5 + 6 - 4 + 2 - 1 23+5-6+4-2+1- 4: 2 + 3 * (5 - 6) - 4 2356-*+4- 5: 2 * 3 ^ 5 * 6 - 4 235^*6*4- 6: (2 + 3) * 6 ^ 2 23+62^* You might also try: 7: ( ( ( ( 2 + 3 - 4 ) / 2 + 8 ) * 3 * ( 4 + 5 ) / 2 / 3 + 9 ) ) 23+4-2/8+3*45+*2/3/9+ Programming Notes: You are to write a well-composed program. The stack routines are to be defined as methods in a class and are to be in a separate file. //A sample c++ program to read a file 1 line at a time #include <iostream> #include <fstream> #include <string> using namespace std; int main() { string aline; ifstream inData; inData.open("infix.data"); while ( getline(inData,aline) ) { cout << aline << endl; } inData.close(); }
Explanation / Answer
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
// get weight of operators according to precedence
int getHigherWeight(char key) {
switch (key) {
case '/':
case '*': return 2;
case '+':
case '-': return 1;
default : return 0;
}
}
// convert infix expression to postfix using a stack
void infixTOpostfix(char infix[], char postfix[], int size) {
stack<char> st;
int weight;
int i = 0;
int k = 0;
char key;
// iterate over the infix expression
while (i < size) {
key = infix[i];
if (key == '(') {
// simply push the opening parenthesis
st.push(key);
i++;
continue;
}
if (key == ')') {
// if we see a closing parenthesis,
// pop of all the elements and append it to
// the postfix expression till we encounter
// a opening parenthesis
while (!st.empty() && st.top() != '(') {
postfix[k++] = st.top();
st.pop();
}
// pop off the opening parenthesis also
if (!st.empty()) {
st.pop();
}
i++;
continue;
}
weight = getHigherWeight(key);
if (weight == 0) {
// we saw an operand
// simply append it to postfix expression
postfix[k++] = key;
}
else {
// we saw an operator
if (st.empty()) {
// simply push the operator onto stack if
// stack is empty
st.push(key);
}
else {
// pop of all the operators from the stack
while (!st.empty() && st.top() != '(' &&
weight <= getHigherWeight(st.top())) {
postfix[k++] = st.top();
st.pop();
}
// push the current operator onto stack
st.push(key);
}
}
i++;
}
// pop of the remaining operators present in the stack
// and append it to postfix expression
while (!st.empty()) {
postfix[k++] = st.top();
st.pop();
}
postfix[k] = 0; // null terminate the postfix expression
}
// main
int main() {
string aline;
ifstream inData;
inData.open("infix.data");
while ( getline(inData,aline) )
{
char infix[] = aline ;
int size = strlen(infix);
char postfix[size];
infixTOpostfix(infix,postfix,size);
cout<<" Infix Expression :: "<<infix;
cout<<" Postfix Expression :: "<<postfix;
cout<<endl;
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.