ABHI.AKS.SINGH
BAN USER//Solved by basic maths pulled data in stack S
//f(s) = f(operator, s1 , s2)
//s1 and s2 are numbers substack obtained by moving recursively within brackets or after //operators.
//it will work for any length of string as only ListList as been used.
//tested already for many test cases. if still issue, leave a comment.
static boolean ifoperator(String S)
{
boolean b ;
switch (S)
{
case "*":
case "+" :
case "/" :
case "-" :
b = true ; break ;
default:
b = false; break ;
}
return b;
}
static int stack(LinkedList<String> S)
{
//+ ( + 2 3 ) 7
if(ifoperator(S.getFirst()))
{ //System.out.println(S.getFirst());
String op = S.getFirst();
S.removeFirst();
int a = getnum(S);
int b = getnum(S);
return sum(op, a,b);
}
else if (S.getFirst().charAt(0) == '(')
{
S.removeFirst();
int a = stack(S);
return a;
}
else
{
int a = getnum(S);
return a;
}
}
static int getnum(LinkedList<String> S)
{
if(S.isEmpty())
return 0;
if(S.getFirst().charAt(0) == '(' || S.getFirst().charAt(0) == ')')
{
S.removeFirst();
int a = stack(S);
return a;
}
else if(ifoperator(S.getFirst()))
{int a = stack(S);return a;}
else
{
int a = Integer.parseInt(S.getFirst());
S.removeFirst();
return a;
}
}
static int sum(String op, int a , int b)
{ int val = 0 ;
switch (op)
{
case "+":
val = a +b ;
break;
case "-":
val = a - b ;
break;
case "*":
val = a * b ;
break;
case "/":
val = a / b ;
break;
}
//System.out.println("All OKay => " + val);
return val;
}
public static void main (String[] args) throws java.lang.Exception
{
LinkedList<String> exp = new LinkedList<String>();
//String s1 = "+ ( * 5 6 ) ( 7 )";
//String s1 = "* 8 ( + 7 12 )";
//String s1 = "( + + ( + 7 ( * 8 12 ) ) ( * 2 ( * ( + 9 4 ) 7 ) ) 3 )";
String s1 = "( + + + 7 ( * 8 12 ) ( * * 2 ( + 9 4 ) 7 ) 3 )" ;
//7 //96 *2 13 * 7
String temp[] = s1.split(" ");
//System.out.println(temp.length);
//( + ( + 2 3 ) ( * 5 6 ) )
for(int i =0; i<temp.length; i++)
exp.addLast(temp[i]);
System.out.println(stack(exp));
}
1. inorder traversal
2. instead of displaying element just push the element in a stack of size K.
3. once the stack is full, return stack.pop();
a = ll.next ;
b = ll.next.next ;
while (b != null)
{ b=b.next.next;
a =a.next; }
return a;
PS :- there is nothing like middle node for ever number of node .. works only if number of nodes is more than 1.
traverse the nodes from last to first, till nodes are same. The last same node will be the answer.
how to do it ??
Ans -> push nodes of each LL in 2 stacks each while traversing the linked list.
while(s1.node == s2.node)
{s1.pop(); s2.pop();}
1. mark each node you have traversed.
2. the first "marked" node you encounter is the answer.
void parsing(BT b, String S)
- ABHI.AKS.SINGH June 21, 2015{
if(S.charAt(0) == '(')
{
S = S.substring(1);
parsing(b, S);
}
if(S.charAt(0) == ')')
{ S = S.substring(1);
return;
}
else
{
BT c = new BT(S.charAt(0));
b =c;
S = S.substring(1);
if(S.charAt(0) == ')')
{ S = S.substring(1);
return;
}
else if(S.charAt(0) == '(')
{
S = S.substring(1);
BT d = new BT('0');
parsing(d, S);
b.child.add(d);
}
}
}