All possible n pairs of balanced parentheses

#include <cstdio>
#include <list>
#include <string>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;


typedef list<string> List;

/*
Algo:
1. compute all possible balanced expressions of n-1 pairs
2. for each balanced expression of n-1 pairs
for each pos i from 0 to l of an expression
add '('
for each pos j from i + 1 to l
add ')' if expression is balanced
*/
List balParen(int n){

List l;

if(n == 1){

l.push_back("()");

} else if(n == 2){

l.push_back("()()");
l.push_back("(())");

}else {

List l2 = balParen(n - 1); //recursion


for(List::iterator it = l2.begin(); it != l2.end(); ++it){ //for each string of n - 1, add one more pair


for(int i = 0; i < it->length(); ++i){

string s = *it;

s.insert(i, "(");

int n = 0; //n == 0 shows balanced parenthesis

for(int j = i + 1; j < s.length(); ++j ){

if(n == 0){

string s2 = s;

l.push_back(s2.insert(j, ")"));
}

if(s[j] == '(') {

n++;

}else{
n--;
}
}

}
}
}

l.sort();

l.unique();

return l;

}

int main(){

int n;

scanf("%d", &n);

List l = balParen(n);

cout<<l.size()<<endl; //Catalan number Cn = (2n)! / ( (n+1)! n! )

copy(l.begin(), l.end(), ostream_iterator<string>(cout, "\n"));

return 0;
}
Advertisements

Given a linked list and the node values range from 1 to 3.It may contain any number of nodes ,sort the list

#include <cstdlib>
#include <cstdio>

using namespace std;

struct Node {
int data;
struct Node *next;

Node(int _data):data(_data), next(NULL){}
};

typedef Node *List;

/*
 * Algo:
 * Divide the list into 3 different lists,
 * list1 having all 1's, list2 having all 2's and list3 having all 3's
 * Concatenate list1, list2 and list3
 */

List sort(List l){

List start1 = NULL, start2 = NULL, start3 = NULL;

if(!l)
return start1;

Node *n1 = NULL, *n2 = NULL, *n3 = NULL;

while(l){
switch(l->data){
case 1:
if(n1){
n1->next = l;
} else{
start1 = l;
}
n1 = l;


break;
case 2:
if(n2){
n2->next = l;
} else {
start2 = l;
}
n2 = l;


break;
case 3:
if(n3){
n3->next = l;
}else {
start3 = l;
}

n3 = l;

break;
}

l = l->next;
}

if(n1)
n1->next = start2;
if(n2)
n2->next = start3;
if(n3)
n3->next = NULL;

return start1 ? start1 : start2 ? start2 : start3;
}

List append(List l, int n){

Node *node = new Node(n);

if(!l) return node;

Node *p = l;

while(p->next)
p = p->next;

p->next = node;

return l;
}

void print(List l) {

while(l){
printf("%d ", l->data);

l = l->next;
}
printf("\n");
}
/*
 *
 */
int main(int argc, char** argv) {

int n, num;

scanf("%d", &n);

List l = NULL;

for(int i = 0; i < n; ++i){
scanf("%d", &num);
l = append(l, num);
}

print(l);

l = sort(l);

print(l);

return 0;
}

Given an expression E of n numbers with *, + operations and no precedence among the operators, find the max value of E

#include <stdio.h>


int nextNumber(char **s) {

int num = 0;

while(**s != '*' && **s != '+' && **s != '') {

num = num * 10 + (**s - '0');

(*s)++;
}


return num;

}

/*
    Algo:

    Let n0 n1 n2 n3 ... are the numbers in the expression E

    V(E) = max((n0 op V(E1)), ((n0 op n1) op V(E2))),

    Where E1 is the expression starting with n1 and E2 is the expression starting with n2
*/


//Assuming valid expression


int maxExpr(char *s) {

if(*s == '0')
return 0;

int num1 = nextNumber(&s);

char op = *s++;

if(op == '') {
return num1;
}

int val1 = maxExpr(s);

val1 = (op == '*') ? num1 * val1 : num1 + val1;

int num2 = nextNumber(&s);

int val2 = (op == '*') ? num1 * num2 : num1 + num2;

op = *s++;

if(op != '') {

num2 = maxExpr(s);
val2 = (op == '*')? val2 * num2 : val2 + num2;
}

return val2 > val1 ? val2 : val1;

}

/*
    Algo: This is a two pass algorithm
    
    In first pass evaluate all +
    Second pass evaluate all *
*/

int maxExpr(char *s) {

if(*s == '0')
return 0;

int n1, n2, n3 = 0;
char op;

char s2[strlen(s) + 1];
char *p = s2;

//First Pass
if(sscanf(s,"%d%c%d%n",&n1, &op, &n2, &n3) == 1) //only one number
return n1;


do{

if(op == '+') {
n1 += n2;
} else{
p += sprintf(p, "%d*", n1);
n1 = n2;
}

}while(sscanf(s += n3,"%c%d%n", &op, &n2, &n3) != EOF);

sprintf(p, "%d", op == '*' ? n2 : n1);

printf("%s\n", s2);
s = s2;
n3 = 0, n2 = 1;

//Second Pass

if(sscanf(s,"%d%c%d%n",&n1, &op, &n2, &n3) == 1) //reduced to one number
return n1;
do{

n1 *= n2;

}while(sscanf(s += n3,"%c%d%n", &op, &n2, &n3) != EOF);

return n1;

}

int main(){ char *s = "18+3*5+2*9"; printf("%d\n", maxExpr(s));}