Вычисление значения выражения без eval

[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)
}

[Aetae]

А чем eval не угодил то?)
Разумная рекомендация не использовать eval где попало, сделало из неё некое пугало, от которого с ужасом бегут прогеры.))

[B@rmaley.e><e]

Но потом второе умножение почему-то пропускается, и начинает обрабатываться 3+1, и строка равна 9*4.

А Вам не кажется, что искать в том. что Вы вставили на место уже найденного, несколько глупо? Так можно и в бесконечный цикл уйти.

[trikadin]

А вот меня заинтересовало...

<script>
function calculate(str) {
var was_str;
var sum_or_diff=function(sub, a, sign, b) {
 return sign=="-" ? a-b : +a + +b;
};
var mult_or_div= function(sub, a, sign, b) {
 return sign=="*" ? a*b : a/b;
};
var power= function(sub, a, b) {
 return Math.pow(a, b);
};
var match_power= /(-?[\d\.]+)\s*\^\s*(-?[\d\.]+)/g;
var match_mult_div= /(-?[\d\.]+)\s*([\*\/])\s*(-?[\d\.]+)/g;
var match_sum_diff= /(-?[\d\.]+)\s*([\+-])\s*(-?[\d\.]+)/g;

var get_value= function(sub, exp) {
 while(exp.indexOf("^")!==-1)
  exp= exp.replace(match_power, power);
 while(match_mult_div.test(exp))
  exp= exp.replace(match_mult_div, mult_or_div);
 while(match_sum_diff.test(exp))
  exp= exp.replace(match_sum_diff, sum_or_diff);
 return exp;
};
while(str.indexOf("(") !== -1) // убираем скобки
 str=str.replace(/\(([^\(\)]*)\)/g, get_value);

return get_value("", str);

};
</script>
<input value="0.5 * 2 + 7 + -3*2"><input type="button" onclick="alert(calculate(this.previousSibling.value))" value="Посчитать">

Хотя, конечно, лучше через eval c проверкой, как-то так:

<input value="0.5 * 2 + 7 + -3*2"><input type="button" value="Посчитать" onclick="var str=this.previousSibling.value; if(str && !/[^\s\d\(\)\.\+\*\/-]/.test(str)) alert(eval(str)); else alert('Введите многочлен!')">

P. S. Ну и, естественно, нужны проверки на баланс скобок, например.

UPD: Допилил степень - "^", как в qBasic'е))
UPD-2: Подумал, вспомнил порядок выполнения мат. операторов, допилил ещё раз...

[Matre]

Aetae, да я просто из интереса захотел сделать вот такой калькулятор.

nasqad, тогда станет ещё сложнее, а так хотя бы всё разбито по блокам.

B@rmaley.e><e, так я же ищу следующий оператор *, а он что-то не находится.
А от бесконечного цикла защищает вот этот костыль:

if (++i > 10000) { 
	alert("Unexpected error"); 
	break; 
}

trikadin, спасибо, так всё работает, только осталось возведение в степень добавить.
Но хотелось бы узнать, почему не работает мой код.

[trikadin]

trikadin, спасибо, так всё работает, только осталось возведение в степень добавить.
Но хотелось бы узнать, почему не работает мой код.

Хрен его знает - я его не пытался анализировать. Меня просто идея заинтересовала, и я решил её реализовать...

[Matre]

Всё, я наконец-то понял, в чём была ошибка.
Когда мы разбираем выражение 3*3*3+1, после первой замены строка имеет вид 9*3+1. Но курсор находится между 9 и *, поэтому скрипт и не может найти 9*3, потому что он его уже прошёл.
В общем-то, так и должно быть. Если бы курсор после замены возвращался бы в начало заменяемого места, то "bbb".replace(/\w/g, "f") давало бы бесконечный цикл. Т.е. b заменился на f, курсор встал перед f, f заменился на f, и так до бесконечности.
Поэтому в 32-ую строку надо было поместить это:

while ( re.test(S) )

Всем спасибо, особенно B@rmaley.e><e за наводку.