Advertisement
Guest User

Untitled

a guest
May 30th, 2015
300
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function countLine(line)
  2. {
  3. /*
  4. PRIORITIES FOR DIFFERENT VALUES:
  5.  
  6. + or - : 0
  7.  
  8. × or ÷ : 1
  9.  
  10. number : Number.POSITEVE_INFINITY
  11.  
  12. Every bracket adds 2 to priority
  13. of actions inside it so that all actions inside brackets
  14. have greater priority than all actions outside brackets
  15.  
  16. Inside the tree the node with lower (or equal)  priority is higher
  17.  
  18. Node is inserted by comparing it's key with root
  19. key and go right if key of node is bigger (BUT NOT EQUAL)
  20. than key of root recursively
  21.  
  22. If node key is lower (OR EQUAL) than root key, node
  23. becomes new root or replace compared node, making it node's left
  24. child
  25. */
  26.  
  27.  
  28. //minimum priority tree
  29. //where nodes are numbers and actions
  30. var Tree =
  31. {
  32.     root: null, //highest node of tree
  33.    
  34.     //insert node with key priority and value value
  35.     set: function (key, value)
  36.     {
  37.         //create node object with
  38.         //key and value parameters
  39.         var node = new Node(key, value);
  40.        
  41.         //if tree is empty, new node will be root
  42.         if (this.root == null) this.root = node;
  43.        
  44.         //else insert node by helper function
  45.         else this.setTo(this.root, node, true);    
  46.     },
  47.    
  48.     //helper function, inserting node
  49.     //to tree by comparing it's key with
  50.     //currentNode key;
  51.     //isRoot indicates, if currentNode is root
  52.     setTo: function (currentNode, node, isRoot)
  53.     {
  54.         //compare keys, if node key is less or equal
  55.         //place it under currentNode so that
  56.         //currentNode is leftChild of node
  57.         if (node.key <= currentNode.key)
  58.         {
  59.             var parent = currentNode.parent;
  60.             node.leftChild = currentNode;
  61.             currentNode.parent = node;
  62.             if (parent != null)
  63.             {
  64.                 node.parent = parent;
  65.                 parent.rightChild = node;
  66.             }
  67.            
  68.             //if currentNode was root
  69.             //and we placed node under it
  70.             //so node is new root
  71.             if (isRoot) this.root = node;
  72.         }
  73.         //if node key is bigger than currentNode key
  74.         //go to currentNode rightChild;
  75.         //if it doesn't exist, place node there
  76.         else if (currentNode.rightChild == null)
  77.         {
  78.             currentNode.rightChild = node;
  79.             node.parent = currentNode;
  80.         }
  81.         //if rightChild exists, go right to insert node
  82.         else this.setTo(currentNode.rightChild, node, false);
  83.     }
  84. }; //end of Tree object
  85.  
  86. //helper constructor, creating node of Tree object
  87. function Node(k, v)
  88. {
  89.     this.key = k;
  90.     this.value = v;
  91.    
  92.     this.leftChild = null;
  93.     this.rightChild = null;
  94.     this.parent = null;
  95. };
  96.  
  97. //function, that counts the Tree by taking
  98. //leftChild of node (number), node (action),
  99. //rightChild of node (number) and counting them
  100. //recursively;
  101. //returns result of counting whole Tree
  102. function countTree(root)
  103. {
  104.     //if Tree is empty, return zero
  105.     if (!root)
  106.         return 0;
  107.        
  108.     //if Tree contains only one node (root), return it's value
  109.     if (root.rightChild == null && root.leftChild == null)
  110.         return root.value;
  111.        
  112.     //count left subtree of root
  113.     var firstNumber = countTree(root.leftChild);
  114.    
  115.     //count right subtree of root
  116.     var secondNumber = countTree(root.rightChild);
  117.    
  118.     //get action value of root
  119.     var action = root.value;
  120.     var result = 0;
  121.    
  122.     //count firstNumber (result of left subtree)
  123.     //and secondNumber (result of right subtree)
  124.     //according to the action value in root
  125.     switch (action)
  126.     {
  127.         case "+":
  128.         {
  129.             //convert into numbers explicitly to prevent
  130.             //string concatenation
  131.             result = Number(firstNumber) + Number(secondNumber);
  132.             break;
  133.         }
  134.        
  135.         case "-":
  136.         {
  137.             result = firstNumber - secondNumber;
  138.             break;
  139.         }
  140.         case "×":
  141.         {
  142.             result = firstNumber * secondNumber;
  143.             break;
  144.         }
  145.         case "÷":
  146.         {
  147.             result = firstNumber / secondNumber;
  148.             break;
  149.         }
  150.     }
  151.     return result;
  152. }
  153.     var N = line.length;                //length of line
  154.     var value = "";                     //number to insert in Tree
  155.     var key = 0;                        //priority of value
  156.    
  157.     var additionalKey = 0;              //additional priority
  158.                                         //for actions inside brackets
  159.     //parse the string char by char
  160.     for (var i = 0; i < N; i++)
  161.     {
  162.         //if char is plus or minus action, put
  163.         //value inside Tree, count key according to brackets
  164.         //and put action inside Tree
  165.         if ("+-".indexOf(line[i]) >= 0)
  166.         {
  167.             Tree.set(Number.POSITIVE_INFINITY, value);
  168.             value = "";
  169.             key = 0 + additionalKey;
  170.             Tree.set(key, line[i]);
  171.         }
  172.        
  173.         //if char is "×" or "÷" action, put value
  174.         //inside Tree, count key according to brackets
  175.         //and put action inside Tree
  176.         else if ("×÷".indexOf(line[i]) >= 0)
  177.         {
  178.             Tree.set(Number.POSITIVE_INFINITY, value);
  179.             value = "";
  180.             key = 1 + additionalKey;
  181.             Tree.set(key, line[i]);
  182.         }
  183.        
  184.         //if char is opening bracket, just
  185.         //increment additionalKey
  186.         else if (line[i] == "(") additionalKey += 2;
  187.        
  188.         //if char is closing bracket, put
  189.         //value in Tree and decrement additionalKey
  190.         else if (line[i] == ")")
  191.         {
  192.             Tree.set(Number.POSITIVE_INFINITY, value);
  193.             value = "";
  194.             additionalKey -= 2;
  195.         }
  196.        
  197.         //if char is digit or dot, put in in value
  198.         //variable
  199.         else value += line[i];
  200.     }
  201.    
  202.     //insert into Tree last value
  203.     if (value)
  204.     {
  205.         Tree.set(Number.POSITIVE_INFINITY, value);
  206.         value = "";
  207.     }
  208.    
  209.     return countTree(Tree.root);
  210. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement