Infix to Postfix
Given a expression convert from infix to postfix.
Please use the BODMAS rule; http://www.math-only-math.com/bodmas-rule.html
In the expression they have only the following characters.
A-Z, (, ), +, -, /, *
Input: A*(B+C)+D
Output: ABC+*D+
Create your own stack to solve this problem.
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "common.h"
#include
char stack[20];
int top=-1;
void push(char a)
{
stack[++top]=a;
}
char pop()
{
if(top==-1)
return -1;
else
return stack[top--];
}
int priority(char x)
{
if(x=='(')
return 0;
if(x=='+'||x=='-')
return 1;
if(x=='*'||x=='/')
return 2;
}
char * func(char * str){
if(str==NULL)
return NULL;
int len=strlen(str);
char *output=(char*)malloc(len*sizeof(char));
int i=0,j=0;
char ch,a;
for(i=0;i='A'&&str[i]<='Z')
output[j++]=str[i];
else if(a=='(')
push(a);
else if(a==')')
{
while((ch=pop())!='(')
output[j++]=ch;
}
else
{
while(priority(stack[top])>=priority(a))
output[j++]=pop();
push(a);
}
}
while(top!=-1)
output[j++]=pop();
return output;
}
Implement a Q using LinkedList. You need to implement enqueue and dequeue function.
When getHeadOfLinkedList is called, return the head of the linked list.
When enqueue is called, insert the items in list at the head.
When the Q is empty and dequeue is called return 0
When the Q is empty, GetMax and GetMin should return 0
GetMax should return the MAX element in the Q and it should NOT remove the element out.
Input:
ENQUEUE 4 ENQUEUE 6 ENQUEUE 8 DEQUEUE
GETMAX should return: 8
Input: ENQUEUE 3 DEQUEUE DEQUEUE DEQUEUE ENQUEUE 5
GETMAX should return 5
// here is the definition
public class SintNode {
public int num;
public SintNode nextNode;
public SintNode(int num){
this.num = num;
}
}
//Here is the Definition of SintNode for C Language
struct SintNode {
int num;
struct SintNode * nextNode;
};
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "common.h"
#include "answer.h"
#include
struct SintNode * head = NULL;
struct SintNode * getHeadOfLinkedList() {
return head;
}
int getMax(){
if(head==NULL)
{
return 0;
}
else{
int m;
struct SintNode *t=head;
m=t->num;
while(t!='\0')
{
if(mnum)
{
m=t->num;
}
t=t->nextNode;
}
return m;
}
}
void enQueue(int num) {
struct SintNode *newnode=(struct SintNode *)malloc(sizeof(struct SintNode));
if(newnode==NULL){
exit(0);
}
newnode->num=num;
if(head==NULL)
{
newnode->nextNode=NULL;
head=newnode;
}
else
{
newnode->nextNode=head;
head=newnode;
}
}
int deQueue() {
struct SintNode *temp =head;
struct SintNode *t;
if(head==NULL)
{
return 0;
}
else if(head->nextNode==NULL)
{
head=NULL;
}
else
{
while(temp->nextNode != NULL)
{
t=temp;
temp=temp->nextNode;
}
free(t->nextNode);
t->nextNode=NULL;
}
}
void push(int num) {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
}
int pop() {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
int getMin(){
return 0;
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
}
Implement a Q using LinkedList. You need to implement enqueue and dequeue function.
When getHeadOfLinkedList is called, return the head of the linked list.
When enqueue is called, insert the items in list at the head.
When the Q is empty and dequeue is called return 0
When the Q is empty, GetMax and GetMin should return 0
GetMin should return the MIN element in the Q and it should NOT remove the element out.
Input:
ENQUEUE 4 ENQUEUE 6 ENQUEUE 8 DEQUEUE
GETMAX should return: 6
Input: PUSH 3 POP POP POP PUSH 5
GETMAX should return 5
// here is the definition
public class SintNode {
public int num;
public SintNode nextNode;
public SintNode(int num){
this.num = num;
}
}
//Here is the Definition of SintNode for C Language
struct SintNode {
int num;
struct SintNode * nextNode;
};
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "common.h"
#include "answer.h"
#include
struct SintNode * head = NULL;
struct SintNode *temp;
struct SintNode * getHeadOfLinkedList() {
return head;
}
int getMax(){
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
void enQueue(int num) {
struct SintNode *newnode=(struct SintNode *)malloc(sizeof(struct SintNode));
if(newnode==NULL)
{
exit(0);
}
newnode->num=num;
if(head==NULL)
{
newnode->nextNode=NULL;
head=newnode;
}
else
{
newnode->nextNode=head;
head=newnode;
}
}
int deQueue() {
if(head==NULL)
{
return 0;
}
else if(head->nextNode==NULL)
{
head=NULL;
}
else{
temp=head;
struct SintNode *t;
while(temp->nextNode!=NULL)
{
t=temp;
temp=temp->nextNode;
}
free(t->nextNode);
t->nextNode=NULL;
}
}
void push(int num) {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
}
int pop() {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
int getMin(){
if(head==NULL)
{
return 0;
}
else
{
struct SintNode *t=head;
int m;
m=t->num;
while(t!=NULL)
{
if(m>t->num)
{
m=t->num;
}
t=t->nextNode;
}
return m;
}
}
Implement a stack using LinkedList. You need to implement push and pop function.
When getHeadOfLinkedList is called, return the head of the linked list.
When push is called, insert the items in list at the head.
When the stack is empty and pop is called return 0
Input:
PUSH 4 PUSH 6 PUSH 8 POP
getHeadOfLinkedList should return:6->4->NULL
Input: PUSH 3 POP POP POP PUSH 5
getHeadOfLinkedList should return:5->NULL
// here is the definition
public class SintNode {
public int num;
public SintNode nextNode;
public SintNode(int num){
this.num = num;
}
}
//Here is the Definition of SintNode for C Language
struct SintNode {
int num;
struct SintNode * nextNode;
};
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "common.h"
#include "answer.h"
#include
struct SintNode * head = NULL;
struct SintNode *top;
struct SintNode * getHeadOfLinkedList() {
return head;
}
int getMax(){
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
void enQueue(int num) {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
}
int deQueue() {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
void push(int num) {
struct SintNode *newnode=(struct SintNode *)malloc(sizeof(struct SintNode));
if(newnode==NULL){
exit(0);
}
newnode->num=num;
newnode->nextNode=head;
head=newnode;
}
int pop() {
if(head==NULL)
{
return 0;
}
struct SintNode *temp;
temp=head;
head=head->nextNode;
free(temp);
}
int getMin(){
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
Implement a stack using LinkedList. You need to implement push and pop function.
When getHeadOfLinkedList is called, return the head of the linked list.
When push is called, insert the items in list at the head.
When the stack is empty and pop is called return 0
When the stack is empty, GetMax and GetMin should return 0
GetMax should return the MAX element in the stack and it should NOT pop the element out.
Input:
PUSH 4 PUSH 6 PUSH 8 POP
GETMAX should return: 6
Input: PUSH 3 POP POP POP PUSH 5
GETMAX should return 5
// here is the definition
public class SintNode {
public int num;
public SintNode nextNode;
public SintNode(int num){
this.num = num;
}
}
//Here is the Definition of SintNode for C Language
struct SintNode {
int num;
struct SintNode * nextNode;
};
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "common.h"
#include "answer.h"
#include
struct SintNode * head = NULL;
struct SintNode * getHeadOfLinkedList() {
return head;
}
int getMax(){
if(head==NULL)
{
return 0;
}
int m=head->num;
struct SintNode *t=head;
while(t!=NULL)
{
if(mnum)
{
m=t->num;
}
t=t->nextNode;
}
return m;
}
void enQueue(int num) {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
}
int deQueue() {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
void push(int num) {
struct SintNode *newnode=(struct SintNode *)malloc(sizeof(struct SintNode));
if(newnode==NULL)
{
exit(0);
}
newnode->num=num;
newnode->nextNode=head;
head=newnode;
}
int pop() {
if(head==NULL)
{
return 0;
}
struct SintNode *temp=head;
head=head->nextNode;
free(temp);
}
int getMin(){
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
Implement a stack using LinkedList. You need to implement push and pop function.
When getHeadOfLinkedList is called, return the head of the linked list.
When push is called, insert the items in list at the head.
When the stack is empty and pop is called return 0
When the stack is empty, GetMax and GetMin should return 0
GetMin should return the MIN element in the stack and it should NOT pop the element out.
Input:
PUSH 4 PUSH 6 PUSH 8 POP
GETMIN should return: 4
Input: PUSH 3 POP POP POP PUSH 5
GETMIN should return 5
// here is the definition
public class SintNode {
public int num;
public SintNode nextNode;
public SintNode(int num){
this.num = num;
}
}
//Here is the Definition of SintNode for C Language
struct SintNode {
int num;
struct SintNode * nextNode;
};
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "common.h"
#include "answer.h"
#include
struct SintNode * head = NULL;
struct SintNode * getHeadOfLinkedList() {
return head;
}
int getMax(){
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
void enQueue(int num) {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
}
int deQueue() {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
void push(int num) {
struct SintNode *newnode=(struct SintNode *)malloc(sizeof(struct SintNode));
if(newnode==NULL)
{
exit(0);
}
newnode->num=num;
newnode->nextNode=head;
head=newnode;
}
int pop() {
if(head==NULL)
{
return 0;
}
struct SintNode *temp=head;
head=head->nextNode;
free(temp);
}
int getMin(){
int m;
if(head==NULL)
{
return 0;
}
m=head->num;
struct SintNode *t=head;
while(t!=NULL)
{
if(m>t->num)
{
m=t->num;
}
t=t->nextNode;
}
return m;
}
You need to implement push, pop, enqueue, dequeue function.
When getHeadOfLinkedList is called, return the head of the linked list.
When push, enqueue is called, insert the items in list at the head.
When the stack is empty and pop, dequeue is called return 0
Dequeue should remove the element from the tail
Input:
PUSH 4 ENQUEUE 6 PUSH 8 POP
getHeadOfLinkedList should return:6->4->NULL
Input: PUSH 3 DEQUEUE POP POP PUSH 5
getHeadOfLinkedList should return:5->NULL
// here is the definition
public class SintNode {
public int num;
public SintNode nextNode;
public SintNode(int num){
this.num = num;
}
}
//Here is the Definition of SintNode for C Language
struct SintNode {
int num;
struct SintNode * nextNode;
};
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "common.h"
#include "answer.h"
#include
struct SintNode * head = NULL;
struct SintNode * getHeadOfLinkedList() {
return head;
}
int getMax(){
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
void enQueue(int num) {
struct SintNode *newnode=(struct SintNode *)malloc(sizeof(struct SintNode));
if(newnode==NULL)
{
exit(0);
}
newnode->num=num;
if(head==NULL)
{
newnode->nextNode=NULL;
head=newnode;
}
else
{
newnode->nextNode=head;
head=newnode;
}
}
int deQueue() {
struct SintNode *t,*temp=head;
if(head==NULL)
{
return 0;
}
else if(head->nextNode==NULL)
{
head=NULL;
}
else
{
while(temp->nextNode!=NULL)
{
t=temp;
temp=temp->nextNode;
}
free(t->nextNode);
t->nextNode=NULL;
}
}
void push(int num) {
struct SintNode *newnode=(struct SintNode *)malloc(sizeof(struct SintNode));
if(newnode==NULL)
{
exit(0);
}
newnode->num=num;
newnode->nextNode=head;
head=newnode;
}
int pop() {
if(head==NULL)
{
return 0;
}
struct SintNode *temp=head;
head=head->nextNode;
free(temp);
}
int getMin(){
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
String has set of parenthesis. Return true if the parenthesis are properly
ordered and closed. For every open bracket,
there should be close bracket in the right sequence.
Brackets will be of type (, {, [, ], }, )
Input: ({{[][]}})
Output: true
Input: {[}]
Output: false // they are not closed in the right sequence
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "common.h"
#include
BOOL func(char * str){
int l=strlen(str);
char stack[l];
int i,top=-1;
for(i=0;str[i]!='\0';i++)
{
if(str[i]=='(' || str[i]=='{'|| str[i]=='[')
{
top++;
stack[top]=str[i];
}
else if(str[i]==']')
{
if(stack[top]=='[')
{
top--;
}
else
{
return false;
}
}
else if(str[i]=='}')
{
if(stack[top]=='{')
{
top--;
}
}
else if(str[i]==')')
{
if(stack[top]=='(')
{
top--;
}
}
}
if(top==-1)
return true;
else
return false;
}
Given a expression convert from postfix to Infix.
Please use the BODMAS rule; http://www.math-only-math.com/bodmas-rule.html
In the expression they have only the following characters.
A-Z, (, ), +, -, /, *
Input: ABC+*D+
Output: ((A*(B+C))+D)
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "common.h"
#include
//char * func(char * str){
//WRITE CODE HERE
char stack[50][50];
int top=-1;
void push(char * x)
{
top++;
strcpy(stack[top],x);
}
char * pop()
{
if(top==-1)
return "-1";
else
return stack[top--];
//top--;
}
char * func(char * str)
{
if(str==NULL)
return NULL;
//int i=0;
int len=strlen(str);
char buf[50];
char * buffer1=( char *)malloc(len*sizeof(str));
char * buffer2=( char *)malloc(len*sizeof(str));
char * buffer=( char *)malloc((len*2)*sizeof(str));
int i=0;
while(str[i]!='\0')
{
if(str[i]=='+' || str[i]=='*' || str[i]=='/' || str[i]=='^' || str[i]=='-')
{
buffer1=pop();
buffer2=pop();
int len=strlen(buffer2);
buffer2[len++]=str[i];
buffer2[len]='\0';
strcat(buffer2,buffer1);
buffer[0]='(';
buffer[1]='\0';
strcat(buffer,buffer2);
len=strlen(buffer);
buffer[len++]=')';
buffer[len]='\0';
push(buffer);
}
else
{
buf[0]=str[i];
buf[1]='\0';
push(buf);
}
i++;
}
strcpy(buffer,pop());
return buffer;
}
Implement a queue using two stack. MyStack has push(int), int pop(), boolean isEmpty() functions.
When the stack is empty and pop is called return 0.
When the queue is empty, deQueue should return 0
Input:
ENQUEUE 4 ENQUEUE 6 DEQUEUE ENQUEUE 8 DEQUEUE
For Programming in C:
//Here is the Definition of stack for C Language
struct stack{
struct SintNode * head;
};
//Here is the Definition of SintNode for C Language
struct SintNode {
int num;
struct SintNode * nextNode;
};
void pushstack(struct stack *,int) can be used to push an integer into the specified stack.
int popstack(struct stack *) can be used to pop an integer from the stack.
int isEmpty(struct stack *) can be used to check whether a stack is empty.(1 = empty. 0 = not empty)
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "common.h"
#include "answer.h"
#include "stack.h"
#include
struct stack s1;
struct stack s2;
struct stack * s1p = &s1;
struct stack * s2p = &s2;
struct SintNode * head = NULL,*rear=NULL;
struct SintNode * getHeadOfLinkedList() {
return head;
}
void initialise(){
initstack(s1p);
initstack(s2p);
}
int getMax(){
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
void enQueue(int num)
{
// struct SintNode *head=NULL,*rear=NULL;
struct SintNode *n=(struct SintNode *)malloc(sizeof(struct SintNode));
n->num=num;
n->nextNode=NULL;
if(head==NULL)
{
head=n;
}
else
{
n->nextNode=head;
head=n;
}
// WRITE YOUR CODE HERE
}
int deQueue()
{ int num=0;
if(head==NULL)
return num;
if(head->nextNode==NULL)
{
num=head->num;
head=NULL;
return num;
}
struct SintNode *temp=head;
struct SintNode*temp1=head->nextNode;
struct SintNode*prev=NULL;
while(temp1!=NULL)
{
prev=temp;
temp=temp1;
temp1=temp1->nextNode;
}
num=temp->num;
prev->nextNode=NULL;
return num;
// WRITE YOUR CODE HERE
}
void push(int num) {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
}
int pop() {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
int getMin(){
return 0;
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
}
struct SintNode * getHead1(){
return getHeadOfLinkedList(s1p);
}
struct SintNode * getHead2(){
return getHeadOfLinkedList(s2p);
}
int getNumofOps(){
return getNumOfOperations(s1p) + getNumOfOperations(s2p);
}
