Infix to Postfix Conversion
In computer science, infix notation is a method of writing arithmetic expressions in which the operands are written before their operators. For example, the infix expression 2 + 3 * 4 means (2 + (3 * 4)).
On the other hand, postfix notation (also known as Reverse Polish Notation or RPN) is a method of writing arithmetic expressions in which each operator follows all of its operands.
Converting an infix expression to a postfix expression can be done using a stack.
Here is an example code implementation in C++:
TEXT/X-C++SRC
1#include <iostream>
2#include <stack>
3using namespace std;
4
5bool isOperator(char c) {
6 if (c == '+' || c == '-' || c == '*' || c == '/') {
7 return true;
8 }
9 return false;
10}
11
12int getPrecedence(char op) {
13 if (op == '+' || op == '-') {
14 return 1;
15 }
16 else if (op == '*' || op == '/') {
17 return 2;
18 }
19 return 0;
20}
21
22string infixToPostfix(string infix) {
23 stack<char> s;
24 string postfix;
25 for (char c : infix) {
26 if (isalnum(c)) {
27 postfix += c;
28 }
29 else if (c == '(') {
30 s.push(c);
31 }
32 else if (c == ')') {
33 while (!s.empty() && s.top() != '(') {
34 postfix += s.top();
35 s.pop();
36 }
37 s.pop();
38 }
39 else if (isOperator(c)) {
40 while (!s.empty() && getPrecedence(c) <= getPrecedence(s.top())) {
41 postfix += s.top();
42 s.pop();
43 }
44 s.push(c);
45 }
46 }
47 while (!s.empty()) {
48 if (s.top() != '(') {
49 postfix += s.top();
50 }
51 s.pop();
52 }
53 return postfix;
54}
55
56int main() {
57 string infix;
58 cout << "Enter an infix expression: ";
59 cin >> infix;
60 string postfix = infixToPostfix(infix);
61 cout << "Postfix expression: " << postfix << endl;
62 return 0;
63}xxxxxxxxxx74
}using namespace std;// Function to check if a character is an operatorbool isOperator(char c) { if (c == '+' || c == '-' || c == '*' || c == '/') { return true; } return false;}// Function to get the precedence of an operatorint getPrecedence(char op) { if (op == '+' || op == '-') { return 1; } else if (op == '*' || op == '/') { return 2; } return 0;}// Function to convert an infix expression to postfixstring infixToPostfix(string infix) { stack<char> s; string postfix; for (char c : infix) { // If character is an operand, add it to the postfix stringOUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment