Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- var expr1 = '(A+B)*(C+D)-E';
- function stack_push(stack, value) {
- stack.unshift(value);
- }
- function stack_pop(stack) {
- return stack.shift();
- }
- function queue_push(queue, value) {
- queue.push(value);
- }
- function queue_pop(queue, value) {
- return queue.pop();
- }
- function to_revert_polish(expression) {
- var stack = [];
- var queue = [];
- var priorities = {
- '+': 1,
- '-': 1,
- '*': 2,
- '/': 2
- };
- const re_operators = /\+|\-|\*|\//;
- const re_operand = /[a-zA-Z0-9]/;
- expression.split('').forEach((token, index) => {
- if (re_operand.test(token)) {
- queue_push(queue, token);
- } else if (re_operators.test(token)) {
- let stack_top = stack[0];
- if (stack_top !== undefined && priorities[token] <= priorities[stack_top] && stack_top !== '(') {
- while(stack.length > 0) {
- queue_push(queue, stack_pop(stack));
- }
- }
- stack_push(stack, token);
- } else if (token === '(') {
- stack_push(stack, token);
- } else if (token === ')') {
- let stack_top = stack[0];
- while (stack_top !== '(') {
- queue_push(queue, stack_pop(stack));
- stack_top = stack[0];
- }
- stack_pop(stack);
- // if stack is empty and left bracket not found, throw error: parenthesis mismatch
- }
- });
- let stack_top = stack[0];
- while (stack_top !== undefined) {
- queue_push(queue, stack_pop(stack));
- stack_top = stack[0];
- }
- return queue.join('');
- }
- console.log(to_revert_polish(expr1) === 'AB+CD+*E-')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement