Please help me with this, and make sure the program works by showing the picture
ID: 3869922 • Letter: P
Question
Please help me with this, and make sure the program works by showing the picture, 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
File1:
/* C++ program to implement basic stack
operations */
#include<bits/stdc++.h>
using namespace std;
#define MAX 1000
class Stack
{
int top;
public:
int a[MAX]; //Maximum size of Stack
Stack() { top = -1; }
bool push(int x);
int pop();
bool isEmpty();
};
bool Stack::push(int x)
{
if (top >= MAX)
{
cout << "Stack Overflow";
return false;
}
else
{
a[++top] = x;
return true;
}
}
int Stack::pop()
{
if (top < 0)
{
cout << "Stack Underflow";
return 0;
}
else
{
int x = a[top--];
return x;
}
}
bool Stack::isEmpty()
{
return (top < 0);
}
File2:
/* C++ implementation to convert infix expression to postfix*/
#include"File1.h"
using namespace std;
//Function to return precedence of operators
//operators : ^ * / + - (
//precedence: 3 2 2 1 1 0
int prec(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}
// The main function to convert infix expression
//to postfix expression
void infixToPostfix(string s)
{
Stack st;
st.push('N');
int l = s.length();
string ns;
for(int i = 0; i < l; i++)
{
// If the scanned character is an operand, add it to output string.
if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z'))
ns+=s[i];
// If the scanned character is an ‘(‘, push it to the stack.
else if(s[i] == '(')
st.push('(');
// If the scanned character is an ‘)’, pop and to output string from the stack
// until an ‘(‘ is encountered.
else if(s[i] == ')')
{
while(st.top() != 'N' && st.top() != '(')
{
char c = st.top();
st.pop();
ns += c;
}
if(st.top() == '(')
{
char c = st.top();
st.pop();
}
}
//If an operator is scanned
else{
while(st.top() != 'N' && prec(s[i]) <= prec(st.top()))
{
char c = st.top();
st.pop();
ns += c;
}
st.push(s[i]);
}
}
//Pop all the remaining elements from the stack
while(st.top() != 'N')
{
char c = st.top();
st.pop();
ns += c;
}
cout << ns << endl;
}
//Driver program to run above functions
int main()
{
string aline;
ifstream inData;
inData.open("infix.data");
while ( getline(inData,aline) )
{
cout << aline << endl;
}
inData.close();
infixToPostfix(aline);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.