Advertisement
Gordon___From

Untitled

Aug 2nd, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. var expr1 = '(A+B)*(C+D)-E';
  2.  
  3.   function stack_push(stack, value) {
  4.     stack.unshift(value);
  5.   }
  6.  
  7.   function stack_pop(stack) {
  8.     return stack.shift();
  9.   }
  10.  
  11.   function queue_push(queue, value) {
  12.     queue.push(value);
  13.   }
  14.  
  15.   function queue_pop(queue, value) {
  16.     return queue.pop();
  17.   }
  18.  
  19.   function to_revert_polish(expression) {
  20.     var stack = [];
  21.     var queue = [];
  22.     var priorities = {
  23.       '+': 1,
  24.       '-': 1,
  25.       '*': 2,
  26.       '/': 2
  27.     };
  28.     const re_operators = /\+|\-|\*|\//;
  29.     const re_operand = /[a-zA-Z0-9]/;
  30.  
  31.     expression.split('').forEach((token, index) => {
  32.       if (re_operand.test(token)) {
  33.         queue_push(queue, token);
  34.       } else if (re_operators.test(token)) {
  35.         let stack_top = stack[0];
  36.  
  37.         if (stack_top !== undefined && priorities[token] <= priorities[stack_top] && stack_top !== '(') {
  38.           while(stack.length > 0) {
  39.             queue_push(queue, stack_pop(stack));
  40.           }
  41.         }
  42.  
  43.         stack_push(stack, token);
  44.       } else if (token === '(') {
  45.         stack_push(stack, token);
  46.       } else if (token === ')') {
  47.         let stack_top = stack[0];
  48.  
  49.         while (stack_top !== '(') {
  50.           queue_push(queue, stack_pop(stack));
  51.           stack_top = stack[0];
  52.         }
  53.         stack_pop(stack);
  54.         // if stack is empty and left bracket not found, throw error: parenthesis mismatch
  55.       }
  56.     });
  57.  
  58.     let stack_top = stack[0];
  59.  
  60.     while (stack_top !== undefined) {
  61.       queue_push(queue, stack_pop(stack));
  62.       stack_top = stack[0];
  63.     }
  64.  
  65.     return queue.join('');
  66.   }
  67.  
  68.   console.log(to_revert_polish(expr1) === 'AB+CD+*E-')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement