Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2013
301
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.55 KB | None | 0 0
  1. package hw3.q04;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.LinkedList;
  6. import java.util.List;
  7.  
  8. public class ExpressionTree
  9. {
  10. public ExpressionTreeNode root;
  11.  
  12.  
  13. public boolean isanumber(ExpressionTreeNode node)
  14. {
  15.  
  16. if((node.data.equals("0")) || (node.data.equals("1")) || (node.data.equals("2"))|| (node.data.equals("3"))||(node.data.equals("4"))||(node.data.equals("5"))||(node.data.equals("6"))||(node.data.equals("7"))||(node.data.equals("8"))||(node.data.equals("9")))
  17. {
  18. return true;
  19. }
  20. return false;
  21. }
  22.  
  23.  
  24.  
  25. public List<String> tostringlist(String prefixExpression) // returns a list of SINGLE strings given a string.
  26. {
  27. List<String> listofstrings = new LinkedList<String>();
  28.  
  29. for (int i = 0; i < prefixExpression.length(); i++) {
  30. char charat = prefixExpression.charAt(i);
  31. String stringat = String.valueOf(charat);
  32. if(!stringat.equals(" "))
  33. {
  34. listofstrings.add(stringat);
  35. }
  36.  
  37.  
  38. }
  39. return listofstrings;
  40. }
  41.  
  42. public List<String> removefirst(List<String> prefixExpression) // returns a list of SINGLE strings given a string.
  43. {
  44. List<String> listofstrings = new LinkedList<String>();
  45.  
  46. for (int i = 1; i < prefixExpression.size(); i++) {
  47. String string = prefixExpression.get(i);
  48.  
  49. listofstrings.add(string);
  50.  
  51.  
  52.  
  53. }
  54. return listofstrings;
  55. }
  56.  
  57. public void addtothisnode(ExpressionTreeNode thenodetoputin) // only adds to the root
  58. {
  59. if(root.left == null)
  60. {
  61. root.left = thenodetoputin;
  62. }
  63. if(root.right == null)
  64. {
  65. root.right = thenodetoputin;
  66. }
  67.  
  68. }
  69.  
  70.  
  71. public ExpressionTree(String prefixExpression)
  72. {
  73. List<String> listofstrings = tostringlist(prefixExpression);
  74.  
  75. for (String currentstring : listofstrings) {
  76. insert( root, currentstring);
  77. }
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87. //createExpressionTree(List<String> listofstrings, ExpressionTreeNode parentroot)
  88. // root = createExpressionTree(listofstrings, null);
  89.  
  90. // ExpressionTreeNode newnode = new ExpressionTreeNode(listofstrings.get(0));
  91. // root = newnode;
  92. // listofstrings = removefirst(listofstrings);
  93. // ExpressionTreeNode newnodel = new ExpressionTreeNode(listofstrings.get(0));
  94. // ExpressionTreeNode newnoder = new ExpressionTreeNode(listofstrings.get(1));
  95. //
  96. // ////
  97. // root.left = createExpressionTree(listofstrings, root);
  98. // root.right = createExpressionTree(listofstrings, root);
  99.  
  100.  
  101.  
  102. //
  103. //
  104. //
  105. // if(newnodel.isanumber(newnodel))
  106. // {
  107. // listofstrings = removefirst(listofstrings);
  108. // root.left = newnodel;
  109. // }
  110. //
  111. // if(!newnodel.isanumber(newnodel))
  112. // {
  113. // root.left = newnodel;
  114. // //????
  115. // listofstrings = removefirst(listofstrings);
  116. // root.left.left = createExpressionTree(listofstrings, root.left);
  117. // root.right.right = createExpressionTree(listofstrings, root.left);
  118. // }
  119. //
  120. //
  121. //
  122. // if(newnoder.isanumber(newnoder))
  123. // {
  124. // root.right = newnoder;
  125. // }
  126. //
  127. //
  128. // if(!newnoder.isanumber(newnoder))
  129. // { root.right = newnoder;
  130. // //????
  131. // listofstrings = removefirst(listofstrings);
  132. // root.left = createExpressionTree(listofstrings, root.right);
  133. // root.right = createExpressionTree(listofstrings, root.right);
  134. // }
  135. //
  136. //
  137.  
  138. }
  139.  
  140.  
  141. //for each STRING in STRINGLIST, run this code ... potentially :(
  142.  
  143. public ExpressionTreeNode lastInsertedNode = new ExpressionTreeNode();
  144. public boolean isLastTokenOperator = false;
  145.  
  146. public void insert(ExpressionTreeNode rootnode, String token) //test + 2 + 1 1
  147. {
  148. ExpressionTreeNode newnode = new ExpressionTreeNode(token);
  149.  
  150. if(root == null)
  151. {
  152. root = newnode;
  153. }
  154. if(isLastTokenOperator) // case 1?
  155. {
  156. //insert into the last inserted left child
  157. rootnode.left = newnode;
  158. }
  159. else // case 2
  160. {
  161. //backtrack: get node with null right child
  162. rootnode.right = newnode;
  163. //insert
  164. }
  165. //maintain
  166. lastInsertedNode = newnode;
  167. if((token.equals("+")) || (token.equals("-")) || (token.equals("*")) || (token.equals("/")))
  168. {
  169. isLastTokenOperator = true;
  170. }
  171. else
  172. {
  173. isLastTokenOperator = false;
  174. }
  175.  
  176.  
  177.  
  178. }
  179.  
  180.  
  181. private ExpressionTreeNode createExpressionTree(List<String> listofstrings, ExpressionTreeNode parentroot)
  182. {
  183. ExpressionTreeNode newnode = new ExpressionTreeNode(listofstrings.get(0));
  184. listofstrings = removefirst(listofstrings);
  185.  
  186.  
  187. if(parentroot == null)
  188. {
  189. root = newnode;
  190. parentroot = root;
  191. createExpressionTree(listofstrings, parentroot);
  192. }
  193.  
  194. if(newnode.isanumber(newnode))
  195. {
  196. parentroot.left = newnode;
  197. }
  198.  
  199. else
  200. {
  201. parentroot.right = newnode;
  202. }
  203.  
  204.  
  205.  
  206.  
  207.  
  208. // ExpressionTreeNode newnoder = new ExpressionTreeNode(listofstrings.get(1));
  209. //
  210. // if(newnodel.isanumber(newnodel))
  211. // {
  212. // listofstrings = removefirst(listofstrings);
  213. // parentroot.left = newnodel;
  214. // }
  215. //
  216. //
  217. // if(!newnodel.isanumber(newnodel))
  218. // {
  219. // listofstrings = removefirst(listofstrings);
  220. // parentroot.left = newnodel;
  221. // parentroot.left = createExpressionTree(listofstrings, parentroot.left);
  222. // parentroot.right = createExpressionTree(listofstrings, parentroot.left);
  223. // }
  224. //
  225. //
  226. // //// RIGHT SIDE ///
  227. // if(newnoder.isanumber(newnoder))
  228. // {
  229. // listofstrings = removefirst(listofstrings);
  230. // parentroot.right = newnoder;
  231. // }
  232. //
  233. // if(!newnoder.isanumber(newnoder))
  234. // {
  235. // listofstrings = removefirst(listofstrings);
  236. // parentroot.right = newnoder;
  237. // parentroot.left = createExpressionTree(listofstrings, parentroot.right);
  238. // parentroot.right = createExpressionTree(listofstrings, parentroot.right);
  239. // }
  240. //
  241. return newnode;
  242. }
  243. //
  244. // public String getExpressionAsInfix()
  245. // {
  246. //
  247. // }
  248. //
  249. // public String getExpressionAsPostfix()
  250. // {
  251. //
  252. // }
  253. //
  254. // public String getExpressionAsPrefix()
  255. // {
  256. //
  257. // }
  258. //
  259. // public String getStructure()
  260. // {
  261. //
  262. // }
  263. //
  264. // public float getValue()
  265. // {
  266. //
  267. // }
  268. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement