|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rodion Gorkovenko 2:5030/1286.6 21 Apr 2003 03:52:00
To : Roman Pavlov
Subject : выражение->дерево
--------------------------------------------------------------------------------
18 Apr 03 21:21, you wrote to All:
RP> Подскажите, плиз алгоритм вычисления выражения.
RP> В виду имеется следующее:
RP> Hапример дано выражение c=(a+b)*d и надо это вычислить. Причем в
RP> действительности выражение будет громоздким. Говорят, что можно это
RP> сделать, занося все операнды и команды (сложения, вычитания..) в дерево.
RP> Киньтесь, доками по этому делу - знакомой очень нужно.
Доки по этому делу часто начинают пускать пыль в глаза, потому что рассматривают
более глубокие темы... По-моему...
Идея типа такой (надо же - месяц назад сочинял, уже запамятовал...)
(Все названия условны)
FORMULA is TERM {+|- TERM} //выражение в {} повторяется 0 или более раз
TERM is ELEMENT {*|/ ELEMENT}
ELEMENT is NUMBER | (FORMULA) //число или подвыражение в скобках
NUMBER is DIGIT {DIGIT} //число состоит из 1 или более цифр
DIGIT is [0..9] //цифра, ясно
Эту могучую идею можно реализовать так, как показано после подписи - правда ваял
я это дело в стесненных обстоятельствах, поэтому родилось оно на ява-скрипте...
Иногда даже работает...
Правда там чуть больше - добавлена операция возведения в степень и унарный
минус. О! кажется там ошибка с возведением в степень - ну, неважно... А так хоть
сейчас в отдельный файл выгрызай и в интернет-эксплорере запускай...
c почтеньем,
Rodion
<html>
<body>
<script language=javascript>
var s1,s2,i1,a=new Object(),ip,neg;
function
PushNumber(n){
a[ip++]=n;
}/*PushNumber*/
function
Evaluate(sign){
if(sign=="+")
a[ip-2]=a[ip-2]+a[ip-1];
else if(sign=="-")
a[ip-2]=a[ip-2]-a[ip-1];
else if(sign=="*")
a[ip-2]=a[ip-2]*a[ip-1];
else if(sign=="/")
a[ip-2]=a[ip-2]/a[ip-1];
else if(sign=="^")
a[ip-2]=Math.pow(a[ip-2],a[ip-1]);
ip--;
}/*Evaluate*/
function
CompEl(){
var ch,keepNeg;
if(s1.charAt(i1)=="("){
i1++;
keepNeg=neg;
neg=0;
CompForm();
neg=keepNeg;
if(s1.charAt(i1)!=")")
alert("Right bracket missing");
i1++;
}/*if*/
else{
if((ch=s1.charAt(i1))<"0"||ch>"9")
alert("Not a number");
s2="";
while(ch>="0"&&ch<="9"){
s2+=ch;
ch=s1.charAt(++i1);
}/*while*/
PushNumber(s2-0);
}/*else*/
if(neg){
neg=0;
a[ip-1]=-a[ip-1];
}/*if*/
}/*CompEl*/
function
CompTerm2(){
var sign;
CompEl();
while((sign=s1.charAt(i1))=="^"){
i1++;
CompEl();
Evaluate(sign);
}/*while*/
}/*CompTerm*/
function
CompTerm(){
var sign;
CompTerm2();
while((sign=s1.charAt(i1))=="*"||sign=="/"){
i1++;
CompTerm2();
Evaluate(sign);
}/*while*/
}/*CompTerm*/
function
CompForm(){
var sign;
if(s1.charAt(i1)=="-"){
neg=1;
i1++;
}/*if*/
CompTerm();
while((sign=s1.charAt(i1))=="+"||sign=="-"){
i1++;
CompTerm();
Evaluate(sign);
}/*while*/
}/*CompForm*/
function
Calculate(){
s1=fi.value;
s2="";
i1=0;
ip=0;
neg=0;
CompForm();
fo.value=a[0];
}/*Calculate*/
</script>
<p>Input formula:<input type=text name=fi value="" size=20></p>
<p>Output formula:<input type=text name=fo value="" size=20></p>
<p><input type=button value="Calculate" onclick="Calculate()"></p>
</body>
</html>
---
* Origin: (2:5030/1286.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
