document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. //In the name of Allah
  2. /*
  3. Using the Stack and Recursive concept, develop a program to convert arithmetic expressions. The program should be able to:
  4.  
  5. -   Convert from infix to postfix
  6. -   Convert infix to prefix
  7.  
  8. The program must prompt user input an arithmetic infix expression for conversion to either prefix or postfix. The conversion option is wholly dependent to the user; either to postfix or prefix.
  9. ---
  10. Infix -> Postfix Rules:
  11. R1: Object operatorStack is empty
  12. R2: if operator, loop until the operator has been pushed onto the operatorStack
  13. -if the operatorStack is empty, or operator have higher precedence than the operator on top of the operatorStack,
  14. -push operator onto operatorStack
  15. -else
  16. -Pop the operatorStack and append that popped operator to the postfix string.
  17. R3: Once reach the end of input string
  18. -loop until operatorStack is empty
  19. -pop the operatorStack object and append that popped operator to the postfix string
  20.  
  21. **Parentheses:
  22. if leftParentheses "(",
  23. pushed onto the operatorStack
  24. but precedence is lower than any other binary operator
  25. else if rightParenthese ")" is found
  26. operator object is repeatedly popped
  27. popped element appended to postfix string
  28. until operator on top is leftParentheses "("
  29. then that operator "(" is popped but not appended
  30. continue scanning the infix string
  31.  
  32. Infix -> Prefix Rules:
  33. iNew algorithm
  34. 1: Reverse the input string
  35. 2: Examine the next element in the input
  36. 3. If it is operand, add it into the output string
  37. 4. If it is closing parenthesis, push it on stack
  38. 5. If it is an operator, then
  39. a. If stack.isEmpty, push operation on stack
  40. b. if the top of the stack is ")", push operator on stack
  41. c. if it has same or higher priority than the top of the stack, push it
  42. d. else pop the operator & add it to output string, repeat 5
  43. 6. If it is "(" pop operator and add them to string s until a ")" is encountered . POP and discard ")"
  44. 7. If there is more input go to step 2
  45. 8. If there is no more input, unstack the remaining operators and add them
  46. 9. Reverse the output string
  47. New algorithm
  48. 1. if operand push into operand stack
  49. 2. if operator
  50. a. if stack is empty or ch="(", push into operator stack
  51. b. if ")", CASE3 until reach "("
  52. c. else, CASE3
  53. 3. if endofexpression, CASE3 until operator stack empty
  54. 4. return the only operand in operandStack
  55.  
  56.  
  57. *Compile: javac 2009147897.java
  58. *Run: java PostfixPrefixApp
  59. Problems still arises1. Can\'t deal with expression with spaces in it E.g. [a + b]. Must use [a+b]
  60. 2. Program are too redundant at certain part: i++; and toPostfix(exp)
  61. 3. Thinking that this is more of the brute way rather than
  62. the inteligent way. Maybe can be simplified
  63. 4. Operators limited to * / + - %
  64. 5. Looping of the program cause unexpected result
  65. 6. toPrefix() is not correct.
  66. e.g: Didn\'t work for (a+b)+c+d, a+(c-h)/(b*d)
  67. */
  68. import java.util.*;
  69. class PostfixPrefixApp{
  70. /**Global Variables**************************************/
  71. private static Stack operatorStack= new Stack();
  72. private static Stack operandStack= new Stack();
  73. private static String postfix="";
  74. private static String prefix="";
  75. private static String temp="";
  76. private static int i=0; //use i to iterate through infix string [exp.charAt(i)]
  77. private static int menu=0;
  78. public static void main (String [] args){
  79. /**Local Variables***************************************/
  80. Scanner scan = new Scanner(System.in);
  81. String infix;
  82. /**Menu**************************************************/
  83. System.out.println ("\\nChanging from infix to postfix or prefix notation.");
  84. System.out.println ("----------");
  85. System.out.println ("Menu");
  86. System.out.println ("----------");
  87. System.out.println ("1. Postfix");
  88. System.out.println ("2. Prefix");
  89. menu = scan.nextInt();
  90.  
  91. /**Postfix***********************************************/
  92. if ( menu == 1){
  93. System.out.println ("Infix to Postfix");
  94. System.out.print ("Enter infix expression: ");
  95. infix = scan.next();
  96. postfix = toPostfix(infix);
  97. System.out.println("Postfix: "+ postfix);
  98. System.out.println ("----------");
  99. }
  100. /**Prefix************************************************/
  101. else if ( menu == 2){
  102. System.out.println ("Infix to Prefix");
  103. System.out.print ("Enter infix expression: ");
  104. infix = scan.next();// Storing the infix string
  105. infix=reverse(toPrefix(reverse(infix)));
  106. System.out.println("Prefix: "+infix);//display prefix string
  107. }
  108. /**Wrong input*******************************************/
  109. else {
  110. System.out.println ("Wrong input.");
  111. System.out.println ("----------");
  112. }
  113.  
  114. System.exit(0);
  115. }
  116. /**toPostfix*********************************************/
  117. public static String toPostfix(String exp){
  118. if (exp.length()==i){
  119. /*
  120. for when the infix has finished being processed
  121. because iterate i for the usage of exp.charAt(i)
  122. */
  123. while (! operatorStack.isEmpty()){
  124. String temp = (String)operatorStack.peek();
  125. if (temp.charAt(0)!=\'(\')//if there is "(" in the operatorStack
  126. postfix+=(String)operatorStack.pop();//pop all element into postfix string
  127. else
  128. operatorStack.pop();//removing "("
  129. }
  130. return postfix; //the last process of the recursion
  131. }
  132. else { //if the infix still being processed
  133. String ch = exp.substring(i,i+1);
  134. if (ch.charAt(0)==\')\'){//if opening parentheses "(", push it into stack
  135. operatorStack.push(ch);
  136. return redundantFunction(exp);// there are same processes that were simplified in this method instead. Refer "Problems arises"
  137. // or refer the method redundantFunction() below
  138. }
  139. else if (ch.charAt(0)==\'(\'){
  140. /*
  141. if found closing parentheses \')\'
  142. loop until reach \'(\'
  143. append poped element of operatorStack into postfix string
  144. remove \'(\' from operatorStack
  145. */
  146. String topOfoperatorStack = (String)operatorStack.peek();
  147. while (! topOfoperatorStack.equals("(")){
  148. //String a=(String)operatorStack.pop();
  149. //System.out.println(a); //for testing process
  150. postfix+=operatorStack.pop();
  151. topOfoperatorStack = (String) operatorStack.peek();
  152. }
  153. operatorStack.pop();
  154. //String c= (String) operatorStack.pop();
  155. //System.out.println("c: "+c); //for testing if we correctly removing (
  156. return redundantFunction(exp);
  157. }
  158. else if (isOperand(ch)){
  159. /*
  160. if an operand a-zA-Z atau digit \\\\d
  161. directly appened to infix
  162. */
  163. postfix+=ch;
  164. return redundantFunction(exp);
  165. }
  166. else if (isOperator(ch)){
  167. /*
  168. if operators
  169. if empty
  170. directly push into operatorStack
  171. else
  172. see top of operatorStack
  173. if higher precendence
  174. directly push into operatorStack
  175. else
  176. pop topOfoperatorStack
  177. append it to postfix string
  178. push current operator into operatorStack
  179. */
  180. if (operatorStack.isEmpty()){
  181. operatorStack.push(ch);
  182. return redundantFunction(exp);
  183. }
  184. else {
  185. String topOfoperatorStack = (String)operatorStack.peek();
  186. if (precendence(ch) > precendence(topOfoperatorStack)){
  187. operatorStack.push(ch);
  188. return redundantFunction(exp);
  189. }
  190. else {
  191. postfix+=(String)operatorStack.pop();
  192. operatorStack.push(ch);
  193. return redundantFunction(exp);
  194. }
  195. }
  196. }
  197. else{
  198. //catching all other possible situation supposedly
  199. return redundantFunction(exp);
  200. }
  201. }
  202. }
  203. /**toPrefix**********************************************/
  204. private static String toPrefix(String exp){
  205. temp="";
  206. if (iprecendence( (String) operatorStack.peek() )) ){
  207. operatorStack.push(ch);
  208. }
  209. else{
  210. temp=CASE3();
  211. operandStack.push(temp);
  212. }
  213. }
  214. //System.out.println(ch);//testing
  215. return redundantFunction(exp);
  216. }
  217. else{
  218. while(! operatorStack.isEmpty()){
  219. temp=CASE3();
  220. operandStack.push(temp);
  221. }
  222. //System.out.println("Who is it? : "+operandStack.peek());//testing
  223. /*if (operandStack.isEmpty())//testing
  224. return "operandStack.isEmpty()";
  225. else*/
  226. return (String) operandStack.pop();
  227. }
  228. }
  229. /**isOperator********************************************/
  230. private static boolean isOperator(String ch){//method to check operator
  231. String operators = "*/%+-";
  232. if (operators.indexOf(ch) != -1)
  233. return true;
  234. else
  235. return false;
  236. }
  237. /**isOperand********************************************/
  238. private static boolean isOperand(String ch){//check if it is alphanumeric - method taken from outside sources
  239. if (ch.matches("[a-zA-Z]|\\\\d"))
  240. return true;
  241. else
  242. return false;
  243. }
  244. /**precedence********************************************/
  245. private static int precendence(String ch){//method that check the precendence of operator and return it
  246.  
  247. //value 1 or 2
  248. String precendence2 = "*/%";
  249. String precendence1 = "+-";
  250. if (precendence2.indexOf(ch) != -1)
  251. return 2;
  252. else if (precendence1.indexOf(ch) != -1)
  253. return 1;
  254. else
  255. return 0;
  256. }
  257. /**redundantFunction********************************************/
  258. private static String redundantFunction(String exp){
  259. /*redundant processes
  260. need i to iterate through infix string while using recursion technique
  261. */
  262. i++;
  263. if (menu==1)
  264. return toPostfix(exp); //the recursion part
  265. else
  266. return toPrefix(exp); //the recursion part
  267. }
  268. /**reverse********************************************/
  269. private static String reverse(String exp){
  270. Stack tempString = new Stack();
  271. for (int index=0;index tempString.push( exp.charAt(index) );
  272. }
  273. exp="";
  274. while (! tempString.isEmpty() ){
  275. exp+= tempString.pop();
  276. }
  277. return exp;
  278. }
  279. private static String CASE3(){
  280. String opt="",oprn1="",oprn2="";
  281. opt += operatorStack.pop();
  282. oprn1 += operandStack.pop();
  283. if (operandStack.isEmpty())
  284. oprn2+="";
  285. else
  286. oprn2 += operandStack.pop();
  287. temp=opt+oprn2+oprn1;
  288. //System.out.println("Temp:"+temp);
  289. return temp;
  290. }
  291. }
');