Простое удаление скобках - на JavaScript


Я решены следующие проблемы:

Вам будет дано математическое строку и вашей задачей будет убрать все скобки следующим образом:

solve("x-(y+z)") = "x-y-z"`

solve("x-(y-z)") = "x-y+z"`

solve("u-(v-w-(x+y))-z") = "u-v+w+x+y-z"`

solve("x-(-y-z)") = "x+y+z"`

Нет пробелов в выражении. Дают только двух операторов: "+" или "-".

Это решение я придумал:

function removeAt(s, index) {
    if (index === s.length - 1) {
        return s.slice(0, -1)
    }
    return s.slice(0, index) + s.slice(index + 1);
}

function insertAt(s, index, str) {
    return s.slice(0, index) + str + s.slice(index);
}

function replaceAt(s, index, chr) {
    if (index > s.length - 1) return s;
    return s.slice(0, index) + chr + s.slice(index + 1);
}

function reverseSigns(s, start, end) {
    for (var i = start; i < end; i++) {
        if (s[i] === '-') {
            s = replaceAt(s, i, '+');
        } else if (s[i] === '+') {
            s = replaceAt(s, i, '-');
        }
    }
    return s;
}

function solve(s) {
    //Get the position of the parenthesis 
    var Close = 0, Open = -1;
    while (s[Close] !== ')' && Close < s.length) {
        if (s[Close] === '(') {
            Open = Close;
        }
        Close++;
    }
    //Check to see if there is any parenthesis 
    if (Open !== -1) {
        //Insert sign before if there is none
        if (s[Open + 1] !== '+' && s[Open + 1] !== '-') {
            s = insertAt(s, Open + 1, '+');
            //'Close' parenthesis has changed --> +1 right
            Close++;
        }
        //Check to see if a sign has to be replaced 
        if (s[Open - 1] === '-') {
            s = reverseSigns(s, Open + 1, Close - 1);
        }
        //Remove the parenthesis 
        s = removeAt(s, Close);
        s = removeAt(s, Open);
        //Remove the sign before paranthesis
        if (s[Open - 1] === '-' || s[Open - 1] === '+') {
            s = removeAt(s, Open - 1);
        }
        //Recursive call
        return solve(s);
        //return s;
    }
    //Remove unnecessary +
    if (s[0] === '+') {
        s = removeAt(s, 0);
    }
    return s;
}

Мне было интересно, если мой код может быть улучшен.



Комментарии
3 ответа

Рекурсия, АСТ, и заключения.

Урок эта проблема абстрактных синтаксических деревьев (АСТ).

Для разбора с читаемым синтаксисом человека в дерево, а затем использовать это дерево, чтобы преобразовать код обратно в удобочитаемой строкой.

То, что вы создали строку мясника, что ломтики строку на куски, бьет их в форму и бросает остатки на тарелку. (Извините, но ваше решение очень неэлегантно)

Примечание стиль

В ECMAScript Конвенции заключается в том, что капиталы только для функций вызывается с новым токеном.

Инкапсулировать функции

При создании решений, которые зависят от набора функций конкретной задаче лучше, чтобы инкапсулировать функции внутри функции main.

Например

function foo() {...}
function bar() {...}
function solve() {
foo();
bar();
}

Лучше

function solve() {
function foo() {...}
function bar() {...}
foo();
bar();
}

Хотя если вы не отстранишь функция solve нужно избегать инкапсуляция внутри рекурсии, так как это позволит создать дополнительные и ненужные закрытия. Так что для рекурсии можно сделать следующее, чтобы инкапсулировать свои государственные функции:

function solve(args) {
function foo() {...}
function bar() {...}
return (function solve() {
if(foo()) { return solve() };
return bar();
})(args);
}

АСТ

Ваше решение слишком сложное.

Что меня поразило, когда я впервые посмотрел в код-это все смещение переменных (s[Open + 1] !== '+' && s[Open + 1] !== '-') в коде я насчитал 13 раз вы добавляете 1 или вычитания 1 из переменной.

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

Когда нужно парсить вложенные строки маркер не изменяет строку. Вы сканировать строку один маркер, в то время, как вы преобразовать каждый маркер "(", ")", "+", "-"и /[a-z]/ для более удобного абстрактной форме.

В компьютерной науке эти обычно называют " АСТ " и представляет входной строки в машиночитаемой форме, а не в читаемую форму, что входная строка является.

Стеки и рекурсии

Рекурсия в ECMAScript его, к сожалению, порочна. В большинстве случаев это, как правило, безопасны, но вы не всегда рискуют вызвать переполнение стека. Вы не можете знать, насколько глубоко вы находитесь в стек вызовов при вызове функции сначала вызывается, так что вы никогда не можете быть уверены, что есть место для завершения итерации.

Как большинство рекурсивных функций всего государства стеки вы можете написать альтернативное решение без рекурсии и через массив, как стек. Это дает множество преимуществ:


  1. Только соответствующие государственные выталкивается в стек

  2. У вас есть гораздо более глубоком уровне итерации

  3. Улучшена производительность и использование памяти.

Рерайт

Это нерекурсивный, необходимо , частичного синтаксического анализатора АСТ и трансформаторов.

Рекурсивный стек реализован в виде массива с push и методов поп-заменить рекурсивный вызов и выходов соответственно.

Важно, как он использует капсулированный общения между ее частями. Обратите внимание, как большинство функции не имеют аргументов и возвращаемых значений. Данные, которые они должны выполнять свою роль в общей общего состояния, i, node, sign, stack и equ. Это уменьшает код источника шума и повышает эффективность исполнения.

Это частичный синтаксический анализатор АСТ / трансформатор, потому что он потребляет дочерние узлы, как он анализирует входной строки. Это потому, что АСТ не нужен и есть прирост производительности, сбрасывая ненужные части АСТ, как мы идем.

Предполагается, что все входные составлено правильно и не содержащие ошибок.

function solve(equ) {
var node, sign = 1, i = 0;
const stack = [];
function push() {
if (node) { stack.push(node) }
node= {sign, vars : []};
sign = 1;
}
function variable(id = equ[i]) {
node.vars.push({sign, id});
sign = 1;
}
function pop() {
const child = node;
node = stack.pop();
for (const v of child.vars) {
sign = v.sign * child.sign;
variable(v.id);
}
}
function result(str = "") {
for (const v of node.vars) { str += ((v.sign * node.sign) < 0 ? "-" : "+") + v.id }
return str[0] === "+" ? str.substr(1) : str;
}
push();
while(i < equ.length){
if (equ[i] === "(") { push() }
else if (equ[i] === ")") { pop() }
else if (equ[i] === "+") { sign *= 1 }
else if (equ[i] === "-") { sign *= -1 }
else { variable() }
i++;
}
return result();
}

1
ответ дан 22 февраля 2018 в 04:02 Источник Поделиться

Я хотел бы сделать это путем перебора маркеры и держать стек текущее состояние (signStack) Как скобочки открываются.



function newSign(current, prev) {
//treat blank as positive
const currentNegative = current[0] == '-';
const prevNegative = prev[0] == '-';
return currentNegative == prevNegative ? '+' : '-';
}

function solve(input) {
let signStack = ['+']; // start by assuming positive
let currentSign = '';

const result = input.replace(/(\+|\-)\(?|\)|\w/g, (match) => {
if (match==')') { // close parenthesis
signStack.shift();
currentSign = signStack[0];
return '';
}

if (match[0] != '+' && match[0] != '-') { // variable
const sign = currentSign;
currentSign = signStack[0];;
return sign + match;
}

const sign = newSign(match, currentSign);
currentSign = sign;
if (match.length > 1) {// open parenthesis
signStack.unshift(sign);
}
return '';
});

if (signStack.length != 1)
throw 'unbalanced parenthesis';

return result;
}

function test(input, expected) {
const result = solve(input);
if (result != expected)
console.log(`Failed: input=${input}, result=${result}, expected=${expected}`);
}

test("x-(y+z)", "x-y-z");
test("x-(y-z)", "x-y+z");
test("u-(v-w-(x+y))-z", "u-v+w+x+y-z");
test("x-(-y-z)", "x+y+z");




3
ответ дан 22 февраля 2018 в 06:02 Источник Поделиться


  1. Используйте правильные названия: Open и Close должны быть в нижнем регистре.

  2. Я немного путают, что Open и Close должны делать.

  3. Зачем тебе рекурсия вместо цикла?

0
ответ дан 22 февраля 2018 в 01:02 Источник Поделиться