#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
class Node {
public:
char data;
Node* next;
};
class LinkedList {
private:
Node* head;
public:
LinkedList() {
head = nullptr;
}
void push(char value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = head;
head = newNode;
}
char pop() {
if (isEmpty()) {
return '\0';
}
Node* temp = head;
char value = temp->data;
head = head->next;
delete temp;
return value;
}
char peek() {
if (isEmpty()) {
return '\0';
}
return head->data;
}
bool isEmpty() {
return head == nullptr;
}
};
int getPrecedence(char op) {
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
return 0;
}
bool isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}
bool isOperand(char ch) {
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
string infixToPrefix(const string& infix) {
stack<char> operators;
LinkedList result;
for (int i = infix.length() - 1; i >= 0; i--) {
char currentChar = infix[i];
if (isOperand(currentChar)) {
result.push(currentChar);
} else if (currentChar == ')') {
operators.push(currentChar);
} else if (currentChar == '(') {
while (!operators.empty() && operators.top() != ')') {
result.push(operators.top());
operators.pop();
}
operators.pop();
} else if (isOperator(currentChar)) {
while (!operators.empty() && getPrecedence(operators.top()) > getPrecedence(currentChar)) {
result.push(operators.top());
operators.pop();
}
operators.push(currentChar);
}
}
while (!operators.empty()) {
result.push(operators.top());
operators.pop();
}
string prefix;
while (!result.isEmpty()) {
prefix += result.pop();
}
return prefix;
}
int main() {
string infixExpression;
cout << "Enter infix expression: ";
getline(cin, infixExpression);
string prefixExpression = infixToPrefix(infixExpression);
cout << "Prefix expression: " << prefixExpression << endl;
return 0;
}