Skip to content

Instantly share code, notes, and snippets.

@cshreyastech

cshreyastech/BSTManupulation

Created May 5, 2015 01:17
Show Gist options
  • Save cshreyastech/725ddf04f67542a8e7fc to your computer and use it in GitHub Desktop.
Save cshreyastech/725ddf04f67542a8e7fc to your computer and use it in GitHub Desktop.
Download ZIP
Raw
BSTManupulation
//insert value to BST
//findPath of a number in BST
//Find Minimum value in BST
//Find Maximum value in BST
//Find Height of BST
//Pre Order Traversal
//Post Order Traversal
//In Order Traversal
//Level Order Traversal
//Find if a Tree in BST
//Delete Node in BST
//Get Successor in BST
//Get Predecessor in BST
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
typedef struct Node Node;
#define CHAR_BIT 8
struct BSTNode {
int data;
struct BSTNode* left;
struct BSTNode* right;
};
/*Function to find minimum of x and y*/
//http://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/
//http://en.cppreference.com/w/cpp/language/operators
int min(int x, int y) {
return y + ((x - y) & ((x - y) >>
(sizeof (int) * CHAR_BIT - 1)));
}
/*Function to find maximum of x and y*/
int max(int x, int y) {
return x - ((x - y) & ((x - y) >>
(sizeof (int) * CHAR_BIT - 1)));
}
struct Node {
struct BSTNode* data;
struct Node* next;
};
void enqueue(struct Node** front, struct Node** rear, struct BSTNode* x) {
struct Node* temp = malloc(sizeof (struct Node));
temp->data = x;
temp->next = NULL;
if (*front == NULL && *rear == NULL) {
*front = *rear = temp;
return;
}
(*rear)->next = temp;
*rear = temp;
}
void dequeue(struct Node** front, struct Node** rear) {
struct Node* temp = *front;
if (front == NULL) {
printf("Queue is empty, no dequeue possible");
return;
}
if (*front == *rear) {
*front = *rear = NULL;
} else
*front = (*front)->next;
free(temp);
}
struct BSTNode* frontValue(struct Node** front) {
if (*front == NULL) {
printf("No node in the list\n");
return;
}
return (*front)->data;
}
bool isEmpty(struct Node** rear) {
if (*rear == NULL) return true;
return false;
}
void print(struct Node* front) {
while (front != NULL) {
printf("%d ", front->data);
front = front->next;
}
printf("\n");
}
struct BSTNode* getNewNode(int x) {
struct BSTNode* newNode = malloc(sizeof (struct BSTNode));
newNode->data = x;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void insertBST(struct BSTNode** root, int x) {
if (*root == NULL) {
struct BSTNode* temp = getNewNode(x);
*root = temp;
return;
}
if (x <= (*root)->data) insertBST(&((*root)->left), x);
else insertBST(&((*root)->right), x);
}
void insertNoNBST(struct BSTNode** root, int x) {
if (*root == NULL) {
struct BSTNode* temp = getNewNode(x);
*root = temp;
return;
}
insertNoNBST(&((*root)->left), x);
}
bool search(struct BSTNode** root, int x) {
if (*root == NULL) return false;
else if (x == (*root)->data) return true;
else if (x < (*root)->data)
search(&((*root)->left), x);
else if (x > (*root)->data)
search(&((*root)->right), x);
return false;
}
struct BSTNode* find(struct BSTNode*root, int data) {
if (root == NULL) return NULL;
else if (root->data == data) return root;
else if (root->data < data) return find(root->right, data);
else return find(root->left, data);
}
int g = 0;
void searchFindPath(struct BSTNode** root, int x, char* path) {
if (*root == NULL) {
if (g == 0)
strcpy(path, "Its a Empty tree");
else
strcpy(path, "Value not found");
return;
} else if (x == (*root)->data) {
g = 1;
return;
// strcat(path, "root");
} else if (x < (*root)->data) {
strcat(path, "-> Left ");
g = 1;
searchFindPath(&((*root)->left), x, path);
} else if (x > (*root)->data) {
strcat(path, "-> Right ");
g = 1;
searchFindPath(&((*root)->right), x, path);
}
}
void findMinimumValue(struct BSTNode** root, char* minValue) {
if (*root == NULL) {
return;
} else if ((*root)->left != NULL)
findMinimumValue(&((*root)->left), minValue);
else {
itoa(((*root)->data), minValue, 10);
}
}
void findMaximumValue(struct BSTNode** root, char* maxValue) {
if (*root == NULL) {
return;
} else if ((*root)->right != NULL)
findMaximumValue(&((*root)->right), maxValue);
else {
itoa(((*root)->data), maxValue, 10);
}
}
int findHeight(struct BSTNode** root) {
if (*root == NULL) return -1;
int leftDepth = findHeight(&((*root)->left));
int rightDepth = findHeight(&((*root)->right));
return (max(leftDepth, rightDepth) + 1);
}
void preOrderTraversal(struct BSTNode** root) {
if (*root == NULL) return;
printf("%d ", (*root)->data);
preOrderTraversal(&((*root)->left));
preOrderTraversal(&((*root)->right));
}
void inOrderTraversal(struct BSTNode** root) {
if (*root == NULL) return;
inOrderTraversal(&((*root)->left));
printf("%d ", (*root)->data);
inOrderTraversal(&((*root)->right));
}
void postOrderTraversal(struct BSTNode** root) {
if (*root == NULL) return;
postOrderTraversal(&((*root)->left));
postOrderTraversal(&((*root)->right));
printf("%d ", (*root)->data);
}
void levelOrderTraversal(struct BSTNode** root) {
struct Node* front = NULL;
struct Node* rear = NULL;
if (*root == NULL) return;
enqueue(&front, &rear, *root);
while (!isEmpty(&rear)) {
struct BSTNode* current = frontValue(&front);
printf("%d ", current->data);
if (current->left != NULL) enqueue(&front, &rear, current->left);
if (current->right != NULL) enqueue(&front, &rear, current->right);
dequeue(&front, &rear);
}
}
bool isBinarySearchTree(struct BSTNode** root, int *temp, int *g) {
if (*root == NULL) {
return;
}
if (*g == 0) return false;
isBinarySearchTree(&((*root)->left), temp, g);
if (*temp > (*root)->data) {
*g = 0;
return false;
}
// printf("temp before assigning: %d\n", *temp);
*temp = (*root)->data;
// printf("temp after assigning: %d\n\n", *temp);
isBinarySearchTree(&((*root)->right), temp, g);
return true;
}
struct BSTNode* findMin(struct BSTNode *root) {
if (root == NULL) return NULL;
while (root->left != NULL) root = root->left;
return root;
}
struct BSTNode* findMax(struct BSTNode *root) {
if (root == NULL) return NULL;
while (root->right != NULL) root = root->right;
return root;
}
struct BSTNode* deleteNode(struct BSTNode* root, int x) {
if (root == NULL) return;
else if (x < root->data)
root->left = deleteNode(root->left, x);
else if (x > root->data)
root->right = deleteNode(root->right, x);
else if (x == root->data) {
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
} else if (root->left == NULL && root->right != NULL) {
struct BSTNode* temp = root;
root = root->right;
free(temp);
} else if (root->right == NULL && root->left != NULL) {
struct BSTNode* temp = root;
root = root->left;
free(temp);
} else {
struct BSTNode* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
return root;
}
void inorderSuccessor(struct BSTNode* root, int x, int *previousLeftTraversal, int *hasLeftTraversed) {
if (root == NULL) return;
else if (x < root->data) {
*previousLeftTraversal = root->data;
*hasLeftTraversed = 1;
inorderSuccessor(root->left, x, previousLeftTraversal, hasLeftTraversed);
} else if (x > root->data) {
// *previousLeftTraversal = root->data;
inorderSuccessor(root->right, x, previousLeftTraversal, hasLeftTraversed);
} else if (x == (root)->data) {
printf("found %d\n", x);
if (root->right != NULL) {
printf("Successor of %d is %d\n", x, (findMin(root->right))->data);
} else if (*hasLeftTraversed == 0 && root->right == NULL) {
printf("%d is the highest value in the tree, no successor\n", x);
} else if (root->right == NULL) {
printf("Successor of %d is %d\n", x, *previousLeftTraversal);
// printf("parent value: %d\n", *parentValue);
// printf("Current value: %d\n", root->data);
}
}
return;
}
struct BSTNode* getSuccessor(struct BSTNode* root, int data) {
struct BSTNode* current = find(root, data);
if (current == NULL) return NULL;
if (current->right != NULL) {
return findMin(current->right);
} else {
struct BSTNode* successor = NULL;
struct BSTNode* ancestor = root;
while (ancestor != current) {
if (current->data < ancestor->data) {
successor = ancestor;
ancestor = ancestor->left;
} else
ancestor = ancestor->right;
}
return successor;
}
}
struct BSTNode* getPredecessor(struct BSTNode* root, int data) {
struct BSTNode* current = find(root, data);
if (current == NULL) return NULL;
if (current->left != NULL) {
return findMax(current->left);
} else {
struct BSTNode* predecessor = NULL;
struct BSTNode* ancestor = root;
while (ancestor != current) {
if (current->data < ancestor->data) {
ancestor = ancestor->left;
} else {
predecessor = ancestor;
ancestor = ancestor->right;
}
}
return predecessor;
}
}
int main() {
struct BSTNode* root = NULL;
insertBST(&root, 15);
insertBST(&root, 10);
insertBST(&root, 20);
insertBST(&root, 12);
insertBST(&root, 8);
insertBST(&root, 6);
insertBST(&root, 11);
insertBST(&root, 25);
insertBST(&root, 27);
insertBST(&root, 17);
insertBST(&root, 16);
// insertNoNBST(&root, 6);
// insertNoNBST(&root, 4);
// insertNoNBST(&root, 10);
// insertNoNBST(&root, 2);
// insertNoNBST(&root, 5);
// insertNoNBST(&root, 7);
// insertNoNBST(&root, 11);
// insertNoNBST(&root, 1);
// insertNoNBST(&root, 3);
// insertNoNBST(&root, 9);
// insertNoNBST(&root, 8);
// int x = 12;
// char path[50] = "root ";
// search(&root, x, path);
// printf("Search result of record %d: %s\n", x, path);
// char s[50] = "This is a string";
// stringAsReference(s);
// printf("s: %s\n", s);
// char minValue[20] = "Empty tree";
// findMinimumValue(&root, minValue);
// printf("Minimum Value in the Tree: %s\n", minValue);
//
//
// char maxValue[20] = "Empty tree";
// findMaximumValue(&root, maxValue);
// printf("Maximum Value in the Tree: %s\n", maxValue);
// printf("Height of Tree: %d\n", findHeight(&root));
// preOrderTraversal(&root);
// inOrderTraversal(&root);
// levelOrderTraversal(&root);
// postOrderTraversal(&root);
// int temp = 0, g = 1;
// printf("\nisBinarySearchTree: %d\n", isBinarySearchTree((&root), &temp, &g));
// int x = 10;
//
// root = deleteNode(root, x);
int x = 16;
// int previousLeftTraversal = 0;
// int hasLeftTraversed = 0;
// inorderSuccessor(root, x, &previousLeftTraversal, &hasLeftTraversed);
printf("Successor: %d\n", getSuccessor(root, x)->data);
printf("Predecessor: %d\n", getPredecessor(root, x)->data);
return (EXIT_SUCCESS);
}
Raw
InfixPrefixPostFix
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
//http://scanftree.com/Data_Structure/postfix-to-infix
typedef struct Node Node;
struct Node {
int data;
struct Node* next;
};
void push(struct Node** top, int x) {
struct Node* temp = malloc(sizeof (struct Node));
temp->data = x;
temp->next = *top;
*top = temp;
}
void pop(struct Node** top) {
struct Node* temp = *top;
*top = (*top)->next;
free(temp);
}
bool isEmpty(struct Node** top) {
if (*top == NULL) return true;
else return false;
}
int topValue(struct Node** top) {
return (*top)->data;
}
void print(struct Node** pointerToString) {
struct Node* temp = *pointerToString;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
struct NodeChar {
char data;
struct NodeChar* next;
};
void pushChar(struct NodeChar** top, char x) {
struct NodeChar* temp = malloc(sizeof (struct NodeChar));
temp->data = x;
temp->next = *top;
*top = temp;
}
void popChar(struct NodeChar** top) {
struct NodeChar* temp = *top;
*top = (*top)->next;
free(temp);
}
bool isEmptyChar(struct NodeChar** top) {
if (*top == NULL) return true;
else return false;
}
char topValueChar(struct NodeChar** top) {
return (*top)->data;
}
void printChar(struct NodeChar** pointerToString) {
struct NodeChar* temp = *pointerToString;
while (temp != NULL) {
printf("%c ", temp->data);
temp = temp->next;
}
printf("\n");
}
struct NodeString {
char data[100];
struct NodeString* next;
};
void pushString(struct NodeString** top, char* x) {
struct NodeString* temp = malloc(sizeof (struct NodeString));
strcpy(temp->data, x);
temp->next = *top;
*top = temp;
}
void popString(struct NodeString** top) {
struct NodeString* temp = *top;
*top = (*top)->next;
free(temp);
}
bool isEmptyString(struct NodeString** top) {
if (*top == NULL) return true;
else return false;
}
char* topValueString(struct NodeString** top) {
return (*top)->data;
}
void printString(struct NodeString** pointerToString) {
struct NodeString* temp = *pointerToString;
while (temp != NULL) {
printf("%s ", temp->data);
temp = temp->next;
}
printf("\n");
}
int evaluate(int a, int b, char operator) {
switch (operator) {
case '/': return a / b;
case '*': return a * b;
case '+': return a + b;
case '-': return a - b;
}
}
// Function to verify whether a character is numeric digit.
bool isOperand(char C) {
if (C >= '0' && C <= '9') return true;
if (C >= 'a' && C <= 'z') return true;
if (C >= 'A' && C <= 'Z') return true;
return false;
}
// Function to verify whether a character is operator symbol or not.
bool isOperator(char C) {
if (C == '+' || C == '-' || C == '*' || C == '/' || C == '$')
return true;
return false;
}
int isRightAssociative(char op) {
if (op == '$') return true;
return false;
}
int getOperatorWeight(char op) {
int weight = -1;
switch (op) {
case '+':
case '-':
weight = 1;
break;
case '*':
case '/':
weight = 2;
break;
case '$':
weight = 3;
break;
}
return weight;
}
int hasHighterPrecedence(char op1, char op2) {
int op1Weight = getOperatorWeight(op1);
int op2Weight = getOperatorWeight(op2);
if (op1Weight == op2Weight) {
if (isRightAssociative(op1)) return false;
else return true;
}
return op1Weight > op2Weight ? true : false;
}
int hasHighterPrecedenceInfixToPrefix(char op1, char op2) {
int op1Weight = getOperatorWeight(op1);
int op2Weight = getOperatorWeight(op2);
if (op1Weight == op2Weight) {
if (isRightAssociative(op1)) return true;
else return false;
}
return op1Weight > op2Weight ? true : false;
}
void evaluatePostFix(char *expression) {
struct Node* top = NULL;
char * pch;
int a, b;
printf("Value of postfix expression %s = ", expression);
// printf("Splitting string \"%s\" into tokens:\n", expression);
// pch = strtok(expression, " ,.-");
pch = strtok(expression, " ");
while (pch != NULL) {
// printf("%s\n", pch);
if ((strcmp(pch, "/") == 0) || (strcmp(pch, "*") == 0) || (strcmp(pch, "+") == 0) || (strcmp(pch, "-") == 0)) {
b = topValue(&top);
pop(&top);
a = topValue(&top);
pop(&top);
// printf("%d %d |%s|\n", b, a, pch);
pch[1] = '\0';
push(&top, evaluate(a, b, pch[0]));
} else {
push(&top, atoi(pch));
}
// pch = strtok(NULL, " ,.-");
pch = strtok(NULL, " ");
}
print(&top);
}
void evaluatePreFix(char *expression, int l) {
struct Node* top = NULL;
printf("Value of prefix expression %s = ", expression);
int x = 0, y = 1, i, g = 0, a, b;
for (i = l - 1; i >= 0; i--) {
if (expression[i] == ' ' && g == 1) {
// printf("x: %d\n", x);
push(&top, x);
x = 0;
y = 1;
g = 0;
} else if (isOperator(expression[i])) {
// printf("isOperator: %c\n", (expression[i]));
a = topValue(&top);
pop(&top);
b = topValue(&top);
pop(&top);
push(&top, evaluate(a, b, expression[i]));
} else if (isOperand(expression[i])) {
x = x + (expression[i] - '0') * y;
y = y * 10;
g = 1;
}
}
print(&top);
}
void infixToPostFix(char *infixExpression, char* postfixExpression, int l) {
struct NodeChar* top = NULL;
int i, j = 0;
printf("InFix: %s\n", infixExpression);
for (i = 0; i < l; i++) {
if (infixExpression[i] == ' ' || infixExpression[i] == ',') continue;
else if (isOperator(infixExpression[i])) {
while (!isEmptyChar(&top) && topValueChar(&top) != '(' && hasHighterPrecedence(topValueChar(&top), infixExpression[i])) {
postfixExpression[j] = topValueChar(&top);
postfixExpression[++j] = ' ';
postfixExpression[++j] = '\0';
popChar(&top);
}
pushChar(&top, infixExpression[i]);
} else if (isOperand(infixExpression[i])) {
// int operand = 0;
while (i < l && isOperand(infixExpression[i])) {
postfixExpression[j] = infixExpression[i];
j++;
i++;
}
postfixExpression[j] = ' ';
postfixExpression[++j] = '\0';
} else if (infixExpression[i] == '(') {
pushChar(&top, infixExpression[i]);
} else if (infixExpression[i] == ')') {
while (!isEmptyChar(&top) && topValueChar(&top) != '(') {
postfixExpression[j] = topValueChar(&top);
postfixExpression[++j] = ' ';
postfixExpression[++j] = '\0';
popChar(&top);
}
popChar(&top);
}
}
while (!isEmptyChar(&top)) {
postfixExpression[j] = topValueChar(&top);
postfixExpression[++j] = ' ';
postfixExpression[++j] = '\0';
popChar(&top);
}
postfixExpression[++j] = '\0';
}
void infixToPreFix(char *infixExpression, char* prefixExpression, int l) {
struct NodeChar* top = NULL;
int i, j = 0;
char temp;
printf("InFix: %s\n", infixExpression);
for (i = 0; i < l / 2; i++) {
temp = infixExpression[i];
infixExpression[i] = infixExpression[(l - 1) - i];
infixExpression[(l - 1) - i] = temp;
}
// printf("InFix: %s\n", infixExpression);
for (i = 0; i < l; i++) {
if (infixExpression[i] == ' ' || infixExpression[i] == ',') continue;
else if (isOperator(infixExpression[i])) {
while (!isEmptyChar(&top) && topValueChar(&top) != ')' && hasHighterPrecedenceInfixToPrefix(topValueChar(&top), infixExpression[i])) {
prefixExpression[j] = topValueChar(&top);
prefixExpression[++j] = ' ';
prefixExpression[++j] = '\0';
popChar(&top);
}
pushChar(&top, infixExpression[i]);
} else if (isOperand(infixExpression[i])) {
// int operand = 0;
while (i < l && isOperand(infixExpression[i])) {
prefixExpression[j] = infixExpression[i];
j++;
i++;
}
prefixExpression[j] = ' ';
prefixExpression[++j] = '\0';
} else if (infixExpression[i] == ')') {
pushChar(&top, infixExpression[i]);
} else if (infixExpression[i] == '(') {
while (!isEmptyChar(&top) && topValueChar(&top) != ')') {
prefixExpression[j] = topValueChar(&top);
prefixExpression[++j] = ' ';
prefixExpression[++j] = '\0';
popChar(&top);
}
popChar(&top);
}
}
while (!isEmptyChar(&top)) {
prefixExpression[j] = topValueChar(&top);
prefixExpression[++j] = ' ';
prefixExpression[++j] = '\0';
popChar(&top);
}
prefixExpression[++j] = '\0';
// printf("prefixExpression length: %d\n", strlen(prefixExpression));
l = strlen(prefixExpression);
for (i = 0; i < l / 2; i++) {
temp = prefixExpression[i];
prefixExpression[i] = prefixExpression[(l - 1) - i];
prefixExpression[(l - 1) - i] = temp;
}
}
void postfixToInfix(char *postfixExpression, char *infixExpression) {
struct NodeString* top = NULL;
char temp[100] = "", c[4] = "";
char lastStackValue[100] = "";
char secondLastStackValue[100] = "";
printf("postfixExpression: %s\n", postfixExpression);
int i = 0, j = 0;
for (i = 0; postfixExpression[i] != '\0'; i++) {
if (postfixExpression[i] == ' ' || postfixExpression[i] == ',') continue;
else if (isOperand(postfixExpression[i])) {
strcpy(temp, "");
j = 0;
while (i < strlen(postfixExpression) && isOperand(postfixExpression[i])) {
temp[j] = postfixExpression[i];
temp[++j] = '\0';
i++;
}
pushString(&top, temp);
} else if (isOperator(postfixExpression[i])) {
strcpy(temp, "");
strcpy(lastStackValue, "");
strcpy(secondLastStackValue, "");
if (isEmptyString(&top)) {
printf("No last value, invalid expression\n");
return;
}
strcpy(lastStackValue, topValueString(&top));
popString(&top);
if (isEmptyString(&top)) {
printf("No second last value, invalid expression\n");
return;
}
strcpy(secondLastStackValue, topValueString(&top));
popString(&top);
strcat(temp, "( ");
strcat(temp, secondLastStackValue);
c[0] = ' ';
c[1] = postfixExpression[i];
c[2] = ' ';
c[3] = '\0';
strcat(temp, c);
strcat(temp, lastStackValue);
strcat(temp, " )");
pushString(&top, temp);
}
}
strcpy(infixExpression, topValueString(&top));
// printString(&top);
}
void prefixToInfix(char *prefixExpression, char *infixExpression) {
struct NodeString* top = NULL;
char temp[100] = "", c[4] = "";
char lastStackValue[100] = "";
char secondLastStackValue[100] = "";
printf("prefixExpression: %s\n", prefixExpression);
int i = 0, j = 0;
for (i = (strlen(prefixExpression) - 1); i > -1; i--) {
if (prefixExpression[i] == ' ' || prefixExpression[i] == ',') continue;
else if (isOperand(prefixExpression[i])) {
strcpy(temp, "");
j = 0;
while (i < strlen(prefixExpression) && isOperand(prefixExpression[i])) {
temp[j] = prefixExpression[i];
temp[++j] = '\0';
i--;
}
pushString(&top, temp);
} else if (isOperator(prefixExpression[i])) {
strcpy(temp, "");
strcpy(lastStackValue, "");
strcpy(secondLastStackValue, "");
if (isEmptyString(&top)) {
printf("No last value, invalid expression\n");
return;
}
strcpy(lastStackValue, topValueString(&top));
popString(&top);
if (isEmptyString(&top)) {
printf("No second last value, invalid expression\n");
return;
}
strcpy(secondLastStackValue, topValueString(&top));
popString(&top);
strcat(temp, "( ");
strcat(temp, lastStackValue);
c[0] = ' ';
c[1] = prefixExpression[i];
c[2] = ' ';
c[3] = '\0';
strcat(temp, c);
strcat(temp, secondLastStackValue);
strcat(temp, " )");
pushString(&top, temp);
}
}
strcpy(infixExpression, topValueString(&top));
// printString(&top);
}
//https://www.youtube.com/watch?v=mGnAuIA2DFU
void postfixToPrefix(char *postfixExpression, char *prefixExpression) {
struct NodeString* top = NULL;
char temp[100] = "", c[3] = "";
char lastStackValue[100] = "";
char secondLastStackValue[100] = "";
printf("postfixExpression: %s\n", postfixExpression);
int i = 0, j = 0;
for (i = 0; postfixExpression[i] != '\0'; i++) {
if (postfixExpression[i] == ' ' || postfixExpression[i] == ',') continue;
else if (isOperand(postfixExpression[i])) {
strcpy(temp, "");
j = 0;
while (i < strlen(postfixExpression) && isOperand(postfixExpression[i])) {
temp[j] = postfixExpression[i];
temp[++j] = '\0';
i++;
}
pushString(&top, temp);
} else if (isOperator(postfixExpression[i])) {
strcpy(temp, "");
strcpy(lastStackValue, "");
strcpy(secondLastStackValue, "");
if (isEmptyString(&top)) {
printf("No last value, invalid expression\n");
return;
}
strcpy(lastStackValue, topValueString(&top));
popString(&top);
if (isEmptyString(&top)) {
printf("No second last value, invalid expression\n");
return;
}
strcpy(secondLastStackValue, topValueString(&top));
popString(&top);
// strcat(temp, "( ");
// c[0] = ' ';
c[0] = postfixExpression[i];
c[1] = ' ';
c[2] = '\0';
strcat(temp, c);
strcat(temp, secondLastStackValue);
strcat(temp, " ");
strcat(temp, lastStackValue);
// strcat(temp, " )");
pushString(&top, temp);
}
}
strcpy(prefixExpression, topValueString(&top));
// printString(&top);
}
//http://www.manojagarwal.co.in/conversion-from-prefix-to-postfix/
void prefixToPostfix(char *prefixExpression, char *postfixExpression) {
struct NodeString* top = NULL;
char temp[100] = "", c[4] = "";
char lastStackValue[100] = "";
char secondLastStackValue[100] = "";
printf("prefixExpression: %s\n", prefixExpression);
int i = 0, j = 0;
for (i = (strlen(prefixExpression) - 1); i > -1; i--) {
if (prefixExpression[i] == ' ' || prefixExpression[i] == ',') continue;
else if (isOperand(prefixExpression[i])) {
strcpy(temp, "");
j = 0;
while (i < strlen(prefixExpression) && isOperand(prefixExpression[i])) {
temp[j] = prefixExpression[i];
temp[++j] = '\0';
i--;
}
pushString(&top, temp);
} else if (isOperator(prefixExpression[i])) {
strcpy(temp, "");
strcpy(lastStackValue, "");
strcpy(secondLastStackValue, "");
if (isEmptyString(&top)) {
printf("No last value, invalid expression\n");
return;
}
strcpy(lastStackValue, topValueString(&top));
popString(&top);
if (isEmptyString(&top)) {
printf("No second last value, invalid expression\n");
return;
}
strcpy(secondLastStackValue, topValueString(&top));
popString(&top);
// strcat(temp, "( ");
strcat(temp, lastStackValue);
strcat(temp, " ");
strcat(temp, secondLastStackValue);
c[0] = ' ';
c[1] = prefixExpression[i];
c[2] = ' ';
c[3] = '\0';
strcat(temp, c);
// strcat(temp, " )");
pushString(&top, temp);
}
}
strcpy(postfixExpression, topValueString(&top));
// printString(&top);
}
int main() {
// char postfixExpression[] = "25 3 * 5 4 * + 9 -";
// char prefixExpression[] = "- + * 25 3 * 5 4 9";
char infixExpression[100] = ""; //"( 1 + 2 ) * ( 3 - 4 ) * 5"; //postfix: A B C * + D E * - //prefix: - + 1 * 2 3 * 4 5
// char postfixExpression[50] = "";
// char prefixExpression[50] = "";
// "1 + 2 * 3 - 4 * 5";
// evaluatePostFix(postFixExpression);
// evaluatePreFix(expression, strlen(preFixExpression));
// infixToPostFix(infixExpression, postfixExpression, strlen(infixExpression));
// printf("postfix: %s\n", postfixExpression);
//
// char postfixExpression[50] = "a b c * + d e / f * -";
// postfixToInfix(postfixExpression, infixExpression);
// printf("infix: %s\n", infixExpression);
// char prefixExpression[50] = "* + a - b c / - d e + - f g h";
// prefixToInfix(prefixExpression, infixExpression);
// printf("infix: %s\n", infixExpression);
// char prefixExpression[] = "";
// char postfixExpression[50] = "4 2 $ 3 * 3 - 8 4 / 1 1 + / +"; //prefix: + 1 * 4 2 3 3 / / 8 4 + 1 1
// postfixToPrefix(postfixExpression, prefixExpression);
// printf("infix: %s\n", prefixExpression);
char prefixExpression[] = "* + A B - C D";
char postfixExpression[50] = "";
prefixToPostfix(prefixExpression, postfixExpression);
printf("postfix: %s\n", postfixExpression);
return (EXIT_SUCCESS);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment