Scribd
Upload
35 views

Algorithm - Assig#3

This C++ program allows the user to choose between converting an infix expression to postfix or prefix notation. It uses a stack data structure to perform the conversions. The program first displays a menu for the user to choose the conversion type. It then takes the infix expression as input and calls the appropriate function to convert it. The result is then printed. The infixToPostfix and infixToPrefix functions implement the conversion algorithms using operator precedence.

Uploaded by

letitolesa472
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
35 views

Algorithm - Assig#3

This C++ program allows the user to choose between converting an infix expression to postfix or prefix notation. It uses a stack data structure to perform the conversions. The program first displays a menu for the user to choose the conversion type. It then takes the infix expression as input and calls the appropriate function to convert it. The result is then printed. The infixToPostfix and infixToPrefix functions implement the conversion algorithms using operator precedence.

Uploaded by

letitolesa472
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 8

dep’t of it Data Structures and Algorithms coarse group assignment 3 (Three)

NOVEMBER 26, 2023


Ambo university
AMBO
Group Members
NAME ID NUMBER
Tedesse Tolasa ………………………………………………………… TUGR/64837/15
Daniel Mekonnen ……………………………………………………… TUGP/65529/15
Genet Tiruneh …………………………………………………………...UGR/64417/14
Ebisa Getacho …………………………………………………………...UGR/61925/14
Elili Temesgen…………………....……………………………………...UGR/61962/14
C++ program with structure and menu allowing the user to
choose between converting infix to postfix and prefix to infix:

#include <iostream>
#include <stack>
#include <string>

using namespace std;

struct Node {
char data;
Node* next;
};

class Stack {
private:
Node* top;

public:
Stack() {
top = nullptr;
}

void push(char c) {
Node* newNode = new Node;
newNode->data = c;
newNode->next = top;
top = newNode;
}
char pop() {
if (isEmpty()) {
return '\0';
}
Node* temp = top;
char c = temp->data;
top = top->next;
delete temp;
return c;
}

bool isEmpty() {
return top == nullptr;
}

char peek() {
if (isEmpty()) {
return '\0';
}
return top->data;
}
};

bool isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
int getPrecedence(char c) {
switch (c) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}

string infixToPostfix(string infix) {


string postfix;
Stack stack;

for (char c : infix) {


if (isalnum(c)) {
postfix += c;
} else if (c == '(') {
stack.push(c);
} else if (c == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
postfix += stack.pop();
}
stack.pop();
} else if (isOperator(c)) {
while (!stack.isEmpty() && getPrecedence(c) <= getPrecedence(stack.peek())) {
postfix += stack.pop();
}
stack.push(c);
}
}

while (!stack.isEmpty()) {
postfix += stack.pop();
}

return postfix;
}

string infixToPrefix(string infix) {


string prefix;
Stack stack;

for (int i = infix.length() - 1; i >= 0; i--) {


char c = infix[i];

if (isalnum(c)) {
prefix = c + prefix;
} else if (c == ')') {
stack.push(c);
} else if (c == '(') {
while (!stack.isEmpty() && stack.peek() != ')') {
prefix = stack.pop() + prefix;
}
stack.pop();
} else if (isOperator(c)) {
while (!stack.isEmpty() && getPrecedence(c) < getPrecedence(stack.peek())) {
prefix = stack.pop() + prefix;
}
stack.push(c);
}
}

while (!stack.isEmpty()) {
prefix = stack.pop() + prefix;
}

return prefix;
}

int main() {
string infix;
int choice;

cout << "Menu:\n";


cout << "1. Convert infix to postfix\n";
cout << "2. Convert infix to prefix\n";
cout << "Enter your choice: ";
cin >> choice;

cin.ignore(); // Ignore the newline character after reading the choice


cout << "Enter the infix expression: ";
getline(cin, infix);

string result;
if (choice == 1) {
result = infixToPostfix(infix);
cout << "Postfix expression: " << result << endl;
} else if (choice == 2) {
result = infixToPrefix(infix);
cout << "Prefix expression: " << result << endl;
} else {
cout << "Invalid choice." << endl;
}

return 0;
}

You might also like