Infix to Prefix in C++: A Comprehensive Guide
Infix notation is a common way of representing mathematical expressions, where the operator is placed in between the operands. For example, in the expression "2 + 3", the operator "+" is placed between the operands "2" and "3". However, this notation can be confusing and difficult to evaluate when dealing with complex expressions or when using a programming language such as C++. In such cases, it is more convenient to use prefix notation, where the operator is placed before the operands. In this article, we will discuss how to convert infix notation to prefix notation in C++.
The first step in converting infix notation to prefix notation is to understand the basic principles of the conversion process. The infix notation is read from left to right, whereas the prefix notation is read from right to left. This means that the order of the operators and operands is reversed in the prefix notation. For example, the infix notation "2 + 3" would be converted to "3 2 +" in prefix notation.
One way to convert infix notation to prefix notation is to use a stack data structure. The stack is used to store the operators and operands as they are read from the infix notation. The stack is initially empty, and the first step is to push the first operand onto the stack. As the infix notation is read from left to right, the next operator is also pushed onto the stack. This process is repeated until the end of the infix notation is reached. At this point, the stack contains all of the operators and operands in the correct order for the prefix notation.
The next step is to pop the operators and operands from the stack and append them to the prefix notation. The process starts with the last operator and operand on the stack, and works its way towards the first operator and operand. The operators are popped first, followed by the operands. This process is repeated until the stack is empty.
To understand the process of converting infix notation to prefix notation in C++, let's take an example of the infix expression "2 + 3 * 4". The corresponding prefix notation for this expression would be "* 3 + 2 4". The following is the C++ code for converting infix to prefix notation:
#include <iostream> #include <stack> using namespace std; string infixToPrefix(string infix) { stack<char> s; string prefix = ""; // Iterate through the infix expression from right to left
for (int i = infix.length() - 1; i >= 0; i--) {
// Ignore spaces and commas if (infix[i] == ' ' || infix[i] == ',') continue; // If the character is an operator, pop operators from the stack and append to prefix else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') { prefix += infix[i]; while (!s.empty()) { prefix += s.top(); s.pop(); }
} // If the character is an operand, append to prefix else if (infix[i] >= '0' && infix[i] <= '9') { prefix += infix[i]; } // If the character is an open parenthesis, push onto stack else if (infix[i] == '(') { s.push(infix[i]); }
// If the character is a close parenthesis, pop operators from stack and append to prefix
// until open parenthesis is reached else if (infix[i] == ')') { while (!s.empty() && s.top() != '(') { prefix += s.top(); s.pop(); } s.pop(); }
} // Pop remaining operators from stack and append to prefix while (!s.empty()) { prefix += s.top(); s.pop(); } // Reverse the prefix expression and return reverse(prefix.begin(), prefix.end()); return prefix; } int main() { string infix = "2 + 3 * 4"; cout << "Infix expression: " << infix << endl;
cout << "Prefix expression: " << infixToPrefix(infix) << endl; return 0; }
In this program, we first define a function "infixToPrefix" that takes in a string as the infix expression. Inside the function, we initialize an empty stack and an empty string for the prefix expression. We then iterate through the infix expression from right to left. If the character is an operator, we pop operators from the stack and append them to the prefix expression. If the character is an operand, we append it to the prefix expression. If the character is an open parenthesis, we push it onto the stack. If the character is a close parenthesis, we pop operators from the stack and append them to the prefix expression until the open parenthesis is reached. After the iteration, we pop remaining operators from the stack and append them to the prefix expression. Finally, we reverse the prefix expression and return it.
