[Matre]

Всем доброго времени суток.

Недавно возникла такая задача: вычислить строку, содержащую арифметическое выражение, без прямого выполнения кода из строки (eval и т.п).

Алгоритм следующий: ищем такие последовательности символов, чтобы было число, оператор и снова число, например, 5*2. Вычисляем значение, т.е. 10, и ставим на место 5*2. Если с обеих сторон скобки, то убираем их из строки. И так, пока не в строке не останется только одно-единственное число, которое и будет ответом.

Проблема в следующем:
Хоть и регулярка, которая ловит последовательность символов число-оператор-число, имеет флаг g, за один проход почему-то обрабатывается только один из нескольких одноимённых операторов, стоящих рядом. Т.е. у меня есть 3*3*3+1, сначала обрабатывается 3*3, потом 3+1, и в итоге мы имеем 9*4, что неверно.

Рассмотрим пример.
Итак, у меня есть выражение 3*3*3+1
По идее, должно обработаться сначала 3*3, тогда строка будет равна 9*3+1. Потом обрабатывается 9*3, строка равна 27+1. Потом 27+1, строка равна 28, ответ получен, всё хорошо.
Но у меня всё работает по-другому.
Сначала обрабатывается 3*3. Это верно. Мы имеем 9*3+1. Но потом второе умножение почему-то пропускается, и начинает обрабатываться 3+1, и строка равна 9*4.

Почему так?
Вот мой код:

var S = "3 * 3 * 3 + 1 * 2", i = 0;
S = S.replace(/\s/g, "");

/*
	Вычисляет выражение вида a + b, a * b, т.е.
	число, оператор и число
*/
function expr(A, O) {
	var D = A.replace(/\(|\)/g, "").split(O);
	if ( O == "+" ) return +D[0] + +D[1];
	if ( O == "-" ) return D[0] - D[1];
	if ( O == "*" ) return D[0] * D[1];
	if ( O == "/" ) return D[0] / D[1];
	if ( O == "^" ) return Math.pow(D[0], D[1]);
}

/*
	Проверяет, не осталось ли в S только число
	Если да — выражение вычислено
*/
function simple() {
	return /^-?\d+(?:\.\d+)?$/.test(S);
}

/*
	Ищем такие последовательности символов, чтобы
	было "число, оператор, число". Если с обеих сторон
	выражения есть скобки, то убираем их
*/
function compute(operator) {
	var re = new RegExp("(\\()?-?\\d+(?:\\.\\d+)?\\" + operator + "-?\\d+(?:\\.\\d+)?(\\))?", "g");
	S = S.replace(re, function (a, b, c) {
		var C, R = "";
		if ( b == undefined || c == undefined )
			C = 1;
		else
			C = 0;
		if (C) R += b || "";
		R += expr(a, operator);
		if (C) R += c || "";
		return R;
	});
}

/*
	В бесконечном цикле обрабатываем все операции
	в порядке их приоритета: ^, *, /, +, -
	Если в S осталось только число, то прерываем цикл
	и показываем результат
*/
while (true) {
	compute("^");
	compute("*"); compute("/");
	compute("+"); compute("-");
	if (simple()) {
		alert(S);
		break;
	}
	if (++i > 10000) {
		alert("Unexpercted error");
		break;
	}alert(S)
}