Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Регистрация Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Блоги > -De-

Оценить эту запись

разбиралка мат. выражений

Запись от -De- размещена 28.12.2010 в 02:41

В рамках программы "убей вечер на ещё один бесполезный велосипед" и воспоминаниях о вузе (кои, вроде, не применились, что, наверное, плохо) сделал разбиралку мат. выражений (гусары, молчать!) на as3.
Как фичи есть переменные и функции. Функции только от одной переменной (можно и от большего, но кому оно надо?).
Т.к. писалось за вечер, то с точки зрения удобства и безопасности использования хреновато, поправить легко, но неинтересно.
Также потому некоторые штуки сделаны неоптимально. Также потому анализатора синтаксической корректности формулы нет (тоже не нужен, ага). Непоправимых политических ошибок быть не должно.
Код AS3:
package  
{
	/**
	 * ...
	 * @author de
	 */
	public class Parser 
	{
		public static var priorities:Array = ["-", "+", "*", "/", "^"];
		public static var bindedVars:Object = new Object();
		public static var bindedFuncs:Object = new Object();
		public function Parser() 
		{
 
		}
		public static function calc(tree:PData):Number {
			var ret:Number;
			if (tree.first && tree.second) {
				ret = calcSign(calc(tree.first), calc(tree.second), tree.sign);
			}
			else if (tree.func != null) {
				ret = tree.func(calc(tree.first));
			}
			else if (!tree.binded) ret = Number(tree.str);
			else ret = bindedVars[tree.str];
			//trace(tree.str, tree.minus ? -ret : ret);
			return tree.minus ? -ret : ret;
		}
		public static function calcSign(val1:Number, val2:Number, sign:String):Number {
			switch(sign) {
				case "-":
					return val1 - val2;
				case "+":
					return val1 + val2;
				case "*":
					return val1 * val2;
				case "/":
					return val1 / val2;
				case "^":
					return Math.pow(val1, val2);
			}
			return Number.NaN;
		}
		public static function getPriority(sign:String):int {
			return priorities.indexOf(sign);
		}
		public static function buildParseTree(node:PData):void {
			var parseStr:String = stripWhites(node.str);
			var ress:Object = {"-3":"function!", "-2":"unary +", "-1":"unary -", "0":"no extra ()", "1":"needs () removement", "2":"IS WRONG"};
			while (true) {
				var cp:int = checkParenthesizes(parseStr);//смотрим, что у нашего выражения со скобками
				//trace(parseStr + " " + ress[cp]);//глазами тоже
				if (cp == 2) throw new Error("incorrect ()");//не тестил, но должно иногда жаловаться
				else if (cp == 1) parseStr = stripParenthesizes(parseStr);//надо убить скобки по краям выражения, шо и делаем
				else if (cp == -1) {//перед выражением стоит унарный минус
					parseStr = parseStr.substr(1);
					node.minus = !node.minus;
				}
				else if (cp == -2) {//перед выражением стоит унарный плюс
					parseStr = parseStr.substr(1);
				}
				else if (cp == -3) {//функция
					var fromPar:int = parseStr.indexOf("(");
					var fname:String = parseStr.substr(0, fromPar);
					if (fname in bindedFuncs) {
						//trace("has such function - "+fname);
						node.func = bindedFuncs[fname];
						var funcArg:PData = new PData(parseStr.substr(fromPar + 1, parseStr.length - fromPar - 2));
						node.first = funcArg;
						buildParseTree(funcArg);
						return;
					}
					else throw new Error("something like unbinded function ("+fname+") found");
				}
				else break;//выражение достаточно голое от скобок
			}
			var breakPlace:int = findBreakPlace(parseStr);//ищем место разбивки
			if (breakPlace == -1) {
				node.str = parseStr;//если не нашли, то наверное и так сойдёт, наверное это тупо число
				if (isNaN(Number(parseStr))) {
					if (parseStr in bindedVars) {
						node.binded = true;
					}
				}
			}
			else {
				node.sign = parseStr.charAt(breakPlace);//какой же собсно знак соединяет левую и правую часть выражения
				var first:PData = new PData(parseStr.substr(0, breakPlace));//левая часть
				var second:PData = new PData(parseStr.substr(breakPlace + 1));//правая часть
				node.first = first;//цепляем детьми к текущему узлу первого
				node.second = second;//и правого
				buildParseTree(first);//и делаем
				buildParseTree(second);//разбивку для них
			}
		}
		public static function findBreakPlace(str:String):int {
			var ind:int = 0;
			var minPriority:int = int.MAX_VALUE;
			var ret:int = -1;
			var parLevel:int = 0;
			while (ind < str.length) {
				if (str.charAt(ind) == "(") {
					++parLevel;
				}
				else if (str.charAt(ind) == ")") {
					--parLevel;
				}
				if (0 == parLevel && ind > 0) {
					var priorVal:int = getPriority(str.charAt(ind));
					if (priorVal >= 0 && priorVal < minPriority) {
						minPriority = priorVal;
						ret = ind;
					}
				}
				++ind;
			}
			return ret;
		}
		public static function checkParenthesizes(str:String):int {
			//0 - fine, strip is useless, 1 - need to strip, 2 - open/close mismatch, -1 - has unary -, -2 has unary +, -3 - is function
			if (str.charAt(0) == "-") {
				return -1;
			}
			if (str.charAt(0) == "+") {
				return -2;
			}
			if (isFunction(str)) return -3;
			var openNum:int = 0;
			var cantStrip:Boolean = false;
			var nopars:Boolean = true;
			for (var i:int = 0; i < str.length; ++i ) {
				var sati:String = str.charAt(i);
				if (sati == "(") ++openNum;
				if (sati == ")") {
					nopars = false;
					--openNum;
					if (openNum < 0) return 2;
				}
				if (openNum == 0 && i >= 1 && i != str.length-1) cantStrip = true;
			}
			if (openNum != 0) return 2;
			return (cantStrip || nopars) ? 0 : 1;
		}
		public static function stripWhites(str:String):String {
			return str.replace(/[ ,\t,\r,\n]/gi, "");
		}
		public static function isFunction(str:String):Boolean {
			var i:int = str.indexOf("(");
			for each(var sign:String in priorities) if (str.indexOf(sign) != -1 && str.indexOf(sign) < i) return false;
			if ( i >= 1 && str.charAt(str.length - 1) == ")") return true
			return false;
		}
		public static function stripParenthesizes(str:String):String {
			return str.substr(1, str.length - 2);
		}
	}
}
+
Код AS3:
package  
{
	/**
	 * ...
	 * @author de
	 */
	public class PData 
	{
		public var str:String;
		public var value:Number;
		public var minus:Boolean = false;
		public var first:PData;
		public var second:PData;
		public var sign:String;
		public var binded:Boolean = false;
		public var func:Function;
		public function PData(_str:String) 
		{
			str = _str;
		}
 
	}
 
}
Использовать:
Код AS3:
Parser.bindedVars["Math.PI"] = Math.PI;
			Parser.bindedFuncs["Math.sin"] = Math.sin;
			var p:PData = new PData("(5*6 / (Math.PI + 1)) * Math.sin(-5*Math.PI)");
			Parser.buildParseTree(p);
			trace("result is "+Parser.calc(p), "gotta look like ", (5*6 / (Math.PI + 1)) * Math.sin(-5*Math.PI));
Если между двумя вызовами Parser.calc(p) изменить переменную (Parser.bindedVars["Math.PI"]), то значение Parser.calc(p) изменится, так можно строить графики. Если сменить функцию, то не сменится, т.к. было не понятно зачем кому-то так делать)
PS: если вы не поняли, что оно такое и как примерно используется - оно не для вас. Если поняли и по делу нужна какая-то фича, типа человеческого интерфейса к этому или функции многих переменных, то вполне осилю допилить, пишите (если не через год).
Всего комментариев 4

Комментарии

Старый 28.12.2010 05:46 Dukobpa3 вне форума
Dukobpa3
 
Аватар для Dukobpa3
Понравилось:
- bindedVars,
- bindedFunc
- реализация деревом (не потому что это круто, а потому что просто прикольно)

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

//************
Я такую штуку студентом будучи писал. Так обходился двумя стеками(или вообще одним, не помню): операндов и операторов. И из стека извлекал всё по порядку.
Старый 28.12.2010 10:45 Jewelz вне форума
Jewelz
 
Аватар для Jewelz
меньше математики, больше романтики!
Старый 03.01.2011 16:11 anmelegov вне форума
anmelegov
Цитата:
Я такую штуку студентом будучи писал. Так обходился двумя стеками(или вообще одним, не помню): операндов и операторов. И из стека извлекал всё по порядку.
я тоже так делал.. использовал обратную польскую запись чтобы избавиться от скобок. весь парсер получился тогда в 2-х функциях вроде и считать на стеке намного быстрее и проще (для машины)
Старый 05.01.2011 20:36 Mur4ik вне форума
Mur4ik
 

 


Часовой пояс GMT +4, время: 15:09.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2020, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.