Skip to main content

Posts

Showing posts from February, 2014

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)
{

[Binary Tree] Convert a List to a Binary Search Tree of minimal height

The Problem is to create a binary search tree of minimal possible height from a given list of values. The algorithm for this is quite simple:

Sort the items (ascending as well as descending order would do)
Use divide and conquer approach for selecting the items for insertion from the array. Given the list, insert its MID item. Then Partition the list into two: 1 list with items less than the MID and another list with items more than MID and recursively process those lists.
The crux of this function is as follows:

[code language="cpp"]
void _InsertListRec(int *Arr, int StartIndex, int EndIndex)
{
if (StartIndex > EndIndex) return;
int Mid = 0;
Mid = StartIndex + (EndIndex - StartIndex) / 2;
Insert(Arr[Mid]);
_InsertListRec(Arr, StartIndex, Mid - 1);
_InsertListRec(Arr, Mid + 1, EndIndex);
}

[/code]

The full code is as follows:

[code language="cpp"]
class TreeNode
{
public:
TreeNode *Left, *Right;
int NodalValue;

TreeNode(int ValueParam)
{
NodalValue = ValueParam;
Left = Righ…

Anagram Solver

I was coding out a simple string permuting function and I thought of writing out an AnagramSolver just for completion.

The Dictionary can be provided as a wordlist in the form of a text file with a word string per line. You can find several word lists here: http://wordlist.sourceforge.net/

[code language="cpp"]

//Sources
#include<iostream>
#include<string>
#include<fstream>
#include<map>

using namespace std;
class AnagramChecker
{
public:
map<string, bool> Dictionary;
map<string, bool> ResultList;

//Recursive string permuter
void RecurveStrPerm(string Buffer, string Test, int Cur)
{
if (Cur >= Test.length())
{
if (Dictionary.count(Buffer) > 0)
if (ResultList.count(Buffer) == 0)
ResultList[Buffer] = true;
return;
}

for(int i = 0; i <= Buffer.length(); i++)
{
Buffer.insert(i, 1, Test[Cur]);
RecurveStrPerm(Buffer, Test, Cur + 1);
Buffer.erase(i, 1);
}
}

//Build a table out of the strings
void BuildInMemDic()
{
Dictionary.clear();
ifstream DicReader;
DicR…

Some Binary Tree Tricks

This code can do the following:

Depth First Search of a Binary Tree
Breadth First Search of a Binary Tree
Finding sum of numbers formed by a path from root to leaf, in a binary tree that can contain numbers from 0-9.
Mirror a binary tree

I have made use of STL - Queues and vectors here.

[code language="cpp"]</pre>
//Source file

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

class Node
{
public:
int Value;
Node *Left, *Right;

Node(int ValueParam)
{
Value = ValueParam;
Left = Right = NULL;
}
};

class BTree
{
private:
Node* Root;

void _Insert(Node* Ptr, int ValueParam)
{
if (Ptr->Value == ValueParam) return;
if (ValueParam < Ptr->Value)
if (Ptr->Left == NULL) Ptr->Left = new Node(ValueParam);
else _Insert(Ptr->Left,ValueParam);
else if (ValueParam >Ptr->Value)
if (Ptr->Right == NULL) Ptr->Right= new Node(ValueParam);
else _Insert(Ptr->Right, ValueParam);
}

void _DFS(Node* Ptr)
{
if (!Ptr) return;
_DFS(Ptr->Left)…