Skip to main content

InFix to PostFix and PreFix conversion [C++]

To Convert from InFix to Postfix:

  • Print out constants from InFix directly onto the Postfix output

  • For operators, insert them into a stack

  •     Before insertion, make sure to pop out (and print to Postfix output) all operator that have higher precedence than that of the operator currently being inserted.

  • After the entire Infix is processed, flush the stack (if it is not empty) onto the Postfix output


-In case of InFix to Prefix, we must start processing the string from the RIGHT most to LEFT most instead of the usual LEFT to RIGHT.

-This code can handle only numbers from 0-9 (single digit) and +-*/ operators.

[code language="cpp"]
//Evaluate the given expression
#include<iostream>
#include<stack>
#include<vector>
using namespace std;

//Only single digit numbers permitted

int GetPrecedence(char op)
{
switch (op)
{
case '+':
case '-':
return 1;
case '*':
case '/':
default:
return 2;
}
}
char* ConvertInorderToPreOrder(char* InOrderExp, int Size)
{
stack<char> Operators;
vector<char> PostOrderResult;
for (int i = Size-1; i >=0; i--)
if (InOrderExp[i] >= '0'&& InOrderExp[i] <= '9')
PostOrderResult.push_back(InOrderExp[i]);
else
{
while (!Operators.empty() && GetPrecedence(Operators.top()) >= GetPrecedence(InOrderExp[i]))
{
PostOrderResult.push_back(Operators.top());
Operators.pop();
}
Operators.push(InOrderExp[i]);
}
while (!Operators.empty())
{
PostOrderResult.push_back(Operators.top());
Operators.pop();
}
char *ResultString = (char*)malloc(sizeof(char)*PostOrderResult.size()+1);
memset(ResultString, 0, sizeof(char)*(PostOrderResult.size() + 1));
for (int i = 0; i < PostOrderResult.size(); i++)
ResultString[i] = PostOrderResult[i];
ResultString[PostOrderResult.size()] = '\0';
_strrev(ResultString);
return ResultString;
}
char* ConvertInorderToPostOrder(char* InOrderExp, int Size)
{
stack<char> Operators;
vector<char> PostOrderResult;
for (int i = 0; i < Size; i++)
if (InOrderExp[i] >= '0'&& InOrderExp[i] <= '9')
PostOrderResult.push_back(InOrderExp[i]);
else
{
while (!Operators.empty() && GetPrecedence(Operators.top()) >= GetPrecedence(InOrderExp[i]))
{
PostOrderResult.push_back(Operators.top());
Operators.pop();
}
Operators.push(InOrderExp[i]);
}
while (!Operators.empty())
{
PostOrderResult.push_back(Operators.top());
Operators.pop();
}
char *ResultString = (char*)malloc(sizeof(char)*PostOrderResult.size()+1);
memset(ResultString, 0, sizeof(char)*(PostOrderResult.size()+1));
for (int i = 0; i < PostOrderResult.size(); i++)
ResultString[i] = PostOrderResult[i];
ResultString[PostOrderResult.size()] = '\0';
return ResultString;
}

int main()
{

char InExp[] = "2+3*7-5*2-4/2*5+1-4+2/2+1";
cout << "\nInput: " << InExp;
cout << "\n\n";
cout << "\n\PostFix = " << ConvertInorderToPostOrder(InExp, strlen(InExp));
cout << "\n\PreFix = " << ConvertInorderToPreOrder(InExp, strlen(InExp));
cout << "\n\nEnd of code\n\n";
system("pause");
return 0;
}

[/code]

Comments

Post a Comment

Popular posts from this blog

GraphQL

GraphQL What is GraphQL It is a specification laid out by Facebook which proposed an alternative way to query and modify data. Think of it is an as a complimentary of REST/RPC. Now head here and read the  original graphQL documentation . It will take 2-3 hours tops but is a worthy read. This will help you build some impressions on it and help contrast against mine below: Why use GraphQL Core advantage Instead of defining custom backend rpc/rest endpoints for every data-shape, graphql allows you to build a more general endpoint which give frontend/mobile engineers freedom and query and play with the data. It might be less efficient, add a bit more complexity (need for things like  data-loader ), harder to standardize and control client-contracts for. What it looses in complexity and control, it gains in flexibility and freedom - provided your data model is worth of a graphql-ish query  How to tell if my data-model graphql-ish? Are there complex relationships between y

About me

Hi, I'm currently working as a software developer in the logistics industry in San Francisco.  My aim is to impact billions of people's live for the better and make the world a better place. Cheers, Vignesh

Backend - Tech refresher 2019

Hello there As a software engineer, it is important to keep updating your skillsets by learning the latest programming-elements (includes  paradigms,  patterns,  languages,  tools and  frameworks ). This becomes a bit easy if you already working on the cutting edge of something. Even then, it is possible to go too deep and loose breadth. I've taken upon myself to do a tech refresher every year. The intent is to read, experiment and understand these elements by spending anywhere between 4 days to 4 weeks. The ultimate goal is: "do I know most  that I need to know to build a planet-scale backend tech-stack ground up" I'll write up my learnings in posts to help myself (and maybe others) refer it. Here is the initial list I'm thinking about: Redis MySQL, GraphQL Aurora, Mesos, Kubernetes Cadence, SWS Cassandra, MangoDB, NoSQL, MySQL, Spanner, S<, DynDB ELK Flink, Storm, Samza, Spark Hadoop HDFS, Yarn, MapReduce Hive, HBase Kafka, Zookeeper NW: