Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function countLine(line)
- {
- /*
- PRIORITIES FOR DIFFERENT VALUES:
- + or - : 0
- × or ÷ : 1
- number : Number.POSITEVE_INFINITY
- Every bracket adds 2 to priority
- of actions inside it so that all actions inside brackets
- have greater priority than all actions outside brackets
- Inside the tree the node with lower (or equal) priority is higher
- Node is inserted by comparing it's key with root
- key and go right if key of node is bigger (BUT NOT EQUAL)
- than key of root recursively
- If node key is lower (OR EQUAL) than root key, node
- becomes new root or replace compared node, making it node's left
- child
- */
- //minimum priority tree
- //where nodes are numbers and actions
- var Tree =
- {
- root: null, //highest node of tree
- //insert node with key priority and value value
- set: function (key, value)
- {
- //create node object with
- //key and value parameters
- var node = new Node(key, value);
- //if tree is empty, new node will be root
- if (this.root == null) this.root = node;
- //else insert node by helper function
- else this.setTo(this.root, node, true);
- },
- //helper function, inserting node
- //to tree by comparing it's key with
- //currentNode key;
- //isRoot indicates, if currentNode is root
- setTo: function (currentNode, node, isRoot)
- {
- //compare keys, if node key is less or equal
- //place it under currentNode so that
- //currentNode is leftChild of node
- if (node.key <= currentNode.key)
- {
- var parent = currentNode.parent;
- node.leftChild = currentNode;
- currentNode.parent = node;
- if (parent != null)
- {
- node.parent = parent;
- parent.rightChild = node;
- }
- //if currentNode was root
- //and we placed node under it
- //so node is new root
- if (isRoot) this.root = node;
- }
- //if node key is bigger than currentNode key
- //go to currentNode rightChild;
- //if it doesn't exist, place node there
- else if (currentNode.rightChild == null)
- {
- currentNode.rightChild = node;
- node.parent = currentNode;
- }
- //if rightChild exists, go right to insert node
- else this.setTo(currentNode.rightChild, node, false);
- }
- }; //end of Tree object
- //helper constructor, creating node of Tree object
- function Node(k, v)
- {
- this.key = k;
- this.value = v;
- this.leftChild = null;
- this.rightChild = null;
- this.parent = null;
- };
- //function, that counts the Tree by taking
- //leftChild of node (number), node (action),
- //rightChild of node (number) and counting them
- //recursively;
- //returns result of counting whole Tree
- function countTree(root)
- {
- //if Tree is empty, return zero
- if (!root)
- return 0;
- //if Tree contains only one node (root), return it's value
- if (root.rightChild == null && root.leftChild == null)
- return root.value;
- //count left subtree of root
- var firstNumber = countTree(root.leftChild);
- //count right subtree of root
- var secondNumber = countTree(root.rightChild);
- //get action value of root
- var action = root.value;
- var result = 0;
- //count firstNumber (result of left subtree)
- //and secondNumber (result of right subtree)
- //according to the action value in root
- switch (action)
- {
- case "+":
- {
- //convert into numbers explicitly to prevent
- //string concatenation
- result = Number(firstNumber) + Number(secondNumber);
- break;
- }
- case "-":
- {
- result = firstNumber - secondNumber;
- break;
- }
- case "×":
- {
- result = firstNumber * secondNumber;
- break;
- }
- case "÷":
- {
- result = firstNumber / secondNumber;
- break;
- }
- }
- return result;
- }
- var N = line.length; //length of line
- var value = ""; //number to insert in Tree
- var key = 0; //priority of value
- var additionalKey = 0; //additional priority
- //for actions inside brackets
- //parse the string char by char
- for (var i = 0; i < N; i++)
- {
- //if char is plus or minus action, put
- //value inside Tree, count key according to brackets
- //and put action inside Tree
- if ("+-".indexOf(line[i]) >= 0)
- {
- Tree.set(Number.POSITIVE_INFINITY, value);
- value = "";
- key = 0 + additionalKey;
- Tree.set(key, line[i]);
- }
- //if char is "×" or "÷" action, put value
- //inside Tree, count key according to brackets
- //and put action inside Tree
- else if ("×÷".indexOf(line[i]) >= 0)
- {
- Tree.set(Number.POSITIVE_INFINITY, value);
- value = "";
- key = 1 + additionalKey;
- Tree.set(key, line[i]);
- }
- //if char is opening bracket, just
- //increment additionalKey
- else if (line[i] == "(") additionalKey += 2;
- //if char is closing bracket, put
- //value in Tree and decrement additionalKey
- else if (line[i] == ")")
- {
- Tree.set(Number.POSITIVE_INFINITY, value);
- value = "";
- additionalKey -= 2;
- }
- //if char is digit or dot, put in in value
- //variable
- else value += line[i];
- }
- //insert into Tree last value
- if (value)
- {
- Tree.set(Number.POSITIVE_INFINITY, value);
- value = "";
- }
- return countTree(Tree.root);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement