Scribd
Upload
10 views

Data structures-Lab-Programs-II BCA A-PROGRAM 5

Data structures program 2

Uploaded by

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

Data structures-Lab-Programs-II BCA A-PROGRAM 5

Data structures program 2

Uploaded by

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

STUDY MATERIAL

ON

DATA STRUCTURES PRACTICALS


(University of Madras-syllabus 2023-2024)

BCA II YEAR – III SEMESTER

2024

Material Prepared
By
G.T. BAKYARAJ, B.Com., MCA., MBA., MFT.,
Assistant Professor
Department of Computer Science
Peri College of Arts and Science, Mannivakkam, Chennai-600048.
Program 5
Aim: To Convert infix to postfix expressions using c++ program using stack.
Algorithm:
1. Initialize:
 Create an empty stack for operators.
 Initialize an empty string for the postfix expression.
2. Process Each Character:
 If the character is an operand: Append it directly to the postfix expression.
 If the character is an opening parenthesis: Push it onto the stack.
 If the character is a closing parenthesis: Pop characters from the stack to the
postfix expression until an opening parenthesis ( is encountered. Remove the
opening parenthesis from the stack.
3. If the character is an operator:
While the stack is not empty and the precedence of the current operator is less than or
equal to the precedence of the operator at the top of the stack:
a. Pop the operator from the stack to the postfix expression.
b. Push the current operator onto the stack.
4. Finalize:
 Pop any remaining operators from the stack to the postfix expression.
5. Return:
 Return the postfix expression.

Source Code:
#include <iostream> // For input and output
#include <stack> // To use the stack data structure
#include <string> // For handling strings
using namespace std;

// Function to check the precedence of operators


int precedence(char op) {
// Return precedence value: 1 for +/-, 2 for */, 0 for others
return (op == '+' || op == '-') ? 1 : (op == '*' || op == '/') ? 2 : 0;
}

// Function to convert infix expression to postfix


string infixToPostfix(string infix) {
stack<char> st; // Stack to hold operators
string postfix = ""; // Resulting postfix expression

// Iterate through each character of the infix expression


for (char c : infix) {
if (isalnum(c)) // If the character is an operand, add it to postfix
postfix += c;
else if (c == '(') // If it's an opening parenthesis, push to stack
st.push(c);
else if (c == ')') { // If it's a closing parenthesis
// Pop from stack to postfix until an opening parenthesis is found
while (st.top() != '(') { postfix += st.top(); st.pop(); }
st.pop(); // Remove the opening parenthesis from stack
}
else { // If it's an operator
// Pop operators with higher or equal precedence from the stack
while (!st.empty() && precedence(c) <= precedence(st.top())) {
postfix += st.top(); st.pop();
}
st.push(c); // Push the current operator to the stack
}
}

// Pop remaining operators from the stack


while (!st.empty()) { postfix += st.top(); st.pop(); }
return postfix; // Return the postfix expression
}

int main() {
string infix = "A+B*C"; // Example infix expression
// Output the original infix expression
cout << "The Infix expression: " << infix << endl;
// Output the corresponding postfix expression
cout << "The Postfix expression: " << infixToPostfix(infix) << endl;
return 0;
}

Output:

The Infix expression: A+B*C


The Postfix expression: ABC*+

You might also like