Из инфиксной в постфиксную запись. Закрывающая скобка

Question

Пока для выражений с однозначными числами. Благополучно получилось с выражениями без скобок, только со сложением, вычитанием, делением, умножением.
Но добавил цикл while который в случае обнаружения закрывающей скобки выталкивает в выходную строку содержимое стека в обратном порядке до первой встреченной открывающей скобки и получается совсем не то что нужно.

ops = {
  '+': 1,
  '-': 1,
  '/': 2,
  '*': 2
};
//s = '1+2-3+4-5*6+7-4+3*4-9/2+3'.split('');
s = '1*(2+3)'.split('');
stack = [];
out = '';
for (var i = 0; i < s.length; i++) {
  if (!isNaN(s[i])) {
    out += s[i];
  }
  if (isNaN(s[i])) {
    a = stack[stack.length - 1];
    if (stack.length == 0) {
      stack.push(s[i])
    } else {
      if (s[i] == '(') {
        stack.push(s[i])
      }
      if (ops[a] >= ops[s[i]]) {
        out += a;
        console.log('operator', s[i], 'add ' + a);
        console.log('stack before pop', stack);
        stack.pop();
        console.log('stack after pop and before push', stack);
        //выталкиваем из стека в строку
        while (stack.length > 0) {
          out += stack[stack.length - 1];
          stack.pop();
        }
        //выталкиваем из стека в строку
        stack.push(s[i]);
        console.log('stack after  push', stack);
      }
      if (ops[a] < ops[s[i]]) {
        console.log('элемент ' + s[i] + ' > ' + ' кон. стека ' + a);
        stack.push(s[i]);
      }
      // закрывающая скобка
      if (s[i] == ')') {
        while (stack[stack.length - 1] != '(') {
          out += stack[stack.length - 1];
          stack.pop();
        }
        stack.pop();
      }
      // закрывающая скобка
    }
  }
  if (i == s.length - 1 && stack.length != 0) {
    while (stack.length > 0) {
      out += stack[stack.length - 1];
      stack.pop();
    }
  }
  console.log(s[i], 'out', out, 'stack', stack);
}
console.log('out is', out);

Answer 1

В примере в вопросе несколько усложненный код.

что бросается в глаза - проверка и очистка стека происходит внутри цикла, на последней итерации. Вместо этого достаточно помести ее сразу после цикла.
условия свалены в кучу и продолжат проверяться даже тогда, когда уже одно из условий подошло. Для решения достаточно добавлять continue;, чтобы сразу перейти к следующей итерации.
в стеке операций, кроме операций может лежать открывающая скобка, для которой неизвестен приоритет, поэтому, фактически, любое сравнение приоритетов операций с приоритетом скобки всегда даст false. В качестве решения можно просто добавить скобку в операции, с наименьшим приоритетом.

В итоге может получиться такой вариант:

ops = {
  '(': 0,
  '+': 1,
  '-': 1,
  '/': 2,
  '*': 2
};
//s = '1+2-3+4-5*6+7-4+3*4-9/2+3'.split('');
s = '1*(2+3)'.split('');
stack = [];
out = '';
for (var i = 0; i < s.length; i++) {
  if (!isNaN(s[i])) {
    out += s[i];
    continue;
  }
  var a = stack[stack.length - 1];
  if (stack.length == 0) {
    stack.push(s[i]);
    continue;
  }
  if (s[i] == '(') {
    stack.push(s[i]);
    continue;
  }

  if (ops[a] >= ops[s[i]]) {
    out += a;
    console.log('operator', s[i], 'add ' + a);
    console.log('stack before pop', stack);
    stack.pop();
    console.log('stack after pop and before push', stack);
    //выталкиваем из стека в строку
    while (stack.length > 0) {
      out += stack[stack.length - 1];
      stack.pop();
    }
    //выталкиваем из стека в строку
    stack.push(s[i]);
    console.log('stack after  push', stack);
    continue;
  }
  if (ops[a] < ops[s[i]]) {
    console.log('элемент ' + s[i] + ' > ' + ' кон. стека ' + a);
    stack.push(s[i]);
    continue;
  }
  // закрывающая скобка
  if (s[i] == ')') {
    while (stack[stack.length - 1] != '(') {
      out += stack[stack.length - 1];
      stack.pop();
    }
    stack.pop();
  }
  // закрывающая скобка
  console.log(s[i], 'out', out, 'stack', stack);
}
while (stack.length > 0) {
  out += stack[stack.length - 1];
  stack.pop();
}
console.log('out is', out);

Альтернативный вариант:

function seek(stack) {
  return stack[stack.length - 1];
}
ops = {
  '+': 1,
  '-': 1,
  '/': 2,
  '*': 2
};
//s = '1+2-3+4-5*6+7-4+3*4-9/2+3'.split('');
// s = '1*(2+3)'.split('');
s = '1+2*(3-4+5)'.split('');
stack = [];
out = '';
for (var c of s) {
  if (!isNaN(c)) {
    out += c;
    continue;
  }

  if (c in ops) {
    while (ops[seek(stack)] >= ops[c]) {
      out += stack.pop();
    }
    stack.push(c);
    continue;
  }
  if (c === ')') {
    while (stack.length && seek(stack) !== '(') {
      out += stack.pop();
    }
    stack.pop();
    continue;
  }

  stack.push(c);
}

while (stack.length) {
  out += stack.pop();
}

console.log('out is', out);

Answer 2

Разобрался с основной ошибкой и всё же сделал свой собственный рабочий вариант,ура!

ops = {'+':1,
    '-':1,
    '/':2,
    '*':2
};
s = '9*(6+7/2-5+4)*(7+4*5-1)+3'.split('');
stack = [];
out = '';
for (var i = 0; i < s.length; i++) {
    if(!isNaN(s[i])){
        out += s[i];
    }
    if(isNaN(s[i])){
        a = stack[stack.length - 1];
        if(stack.length == 0) {stack.push(s[i])}
        else {
            if (s[i] == '(' || a == '(') {stack.push(s[i])}
            if(ops[a] >= ops[s[i]]) {
                out += a;
                stack.pop();
                openBracket = stack.lastIndexOf('(');
                n = stack.splice(openBracket + 1).reverse().join('');
                out += n
                stack.push(s[i]);
            }
            if(ops[a] < ops[s[i]]) {
                stack.push(s[i]);
            }
            if(s[i] == ')') {
                while(stack[stack.length - 1] != '(') {
                    out += stack[stack.length - 1];
                    stack.pop();
                }
                stack.pop();
            }
        }
    }
}
if (stack.length != 0) {
    while(stack.length > 0) {
        out += stack[stack.length - 1];
        stack.pop();
    }
}
console.log('out is',out);

БЛОГ НА HUSL

Из инфиксной в постфиксную запись. Закрывающая скобка

Ответы (2 шт):