infix to postfix conversion
Best Solution
-------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
int prec(char c) {
if(c == '^') {
return 3;
}
else if(c == '*' || c == '/') {
return 2;
}
else if(c == '+' || c =='-') {
return 1;
}
else {
return -1;
}
}
string infixToPostfix(string s) {
stack<char> st;
string res;
for (int i = 0; i < s.length(); i++)
{
if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
res += s[i];
}
else if(s[i] == '(') {
st.push(s[i]);
}
else if(s[i] == ')') {
while (!st.empty() && st.top() != '(')
{
res += st.top();
st.pop();
}
if(!st.empty()) {
st.pop(); // Popping '(' here
}
}
else {
while (!st.empty() && prec(st.top()) >= prec(s[i]))
{
res += st.top();
st.pop();
}
st.push(s[i]);
}
}
while (!st.empty())
{
res += st.top();
st.pop();
}
return res;
}
int main() {
string exp = "a+b*(c^d-e)^(f+g*h)-i";
cout<<infixToPostfix(exp);
return 0;
}
3.6
5
Begin
initially push some special character say # into the stack
for each character ch from infix expression, do
if ch is alphanumeric character, then
add ch to postfix expression
else if ch = opening parenthesis (, then
push ( into stack
else if ch = ^, then //exponential operator of higher precedence
push ^ into the stack
else if ch = closing parenthesis ), then
while stack is not empty and stack top ≠ (,
do pop and add item from stack to postfix expression
done
pop ( also from the stack
else
while stack is not empty AND precedence of ch <= precedence of stack top element, do
pop and add into postfix expression
done
push the newly coming character.
done
while the stack contains some remaining characters, do
pop and add to the postfix expression
done
return postfix
End
Thank you!
5
3.6
(5 Votes)
0
Are there any code examples left?
New code examples in category C++
