| Назад | Содержание | Вперед |
Про формулы, в которых знак операции стоит между операндами, говорят, что они записаны в инфиксной нотации. Именно такие формулы мы и рассматривали и обрабатывали ранее. Рассмотрим рекурсивные алгоритмы обработки формул, представленных как в инфиксной, так и в других формах.
Представление формулы в прямой польской записи
Во многих случаях можно использовать формулы в бесскобочной записи. В префиксной форме каждый знак операции ставится перед своими операндами. Такую запись иногда называют прямой польской записью. Формула а+b*с в префиксной нотации запишется так +а*bс, а формула (а+b)*с-(d+e)/k следующим образом: -*+abc/+dek. Итак, формула в инфиксной форме А+В, где +— бинарная операция, А и В— операнды (которые в свою очередь могут быть формулами). В префиксной форме формула выглядит так + АВ. В прямой польской записи скобки не требуются, т. к. для каждой операции известны операнды.
Напишем программу, вычисляющую значение формулы, содержащей целые константы, операции +,-,*,%, и представленной в прямой польской записи.
Будем считать, что в формуле встречаются целые константы из диапазона [0; 9]. Формула
((3+7)*(5-2)+7)*2+6
в префиксной форме запишется так:
+*+*+37-5272б.
Результат выполнения сценария приведен на рис. 18.1.
Введенная пользователем формула в префиксной нотации хранится в строке st. Формула просматривается слева направо. Функция cursym обеспечивает выбор очередного символа для анализа. Допустимыми символами являются знаки операций и цифры, выступающие в роли операндов. Является ли очередной символ знаком операции, проверяется функцией sig. Сообщение об ошибке формирует функция
еr.
|
|
| Рис 18.1. Значение формулы в префиксной нотации |
Значение формулы считается с помощью рекурсивной функции vform. Поясним ее работу. Формула в префиксной нотации имеет вид +АВ, следовательно, первый символ обязан быть знаком операции. Запоминаем его в переменной h. Подформула А является формулой в префиксной нотации, поэтому ее значение можно вычислить с помощью той же самой функции vform. Следует выбрать первый символ формулы, вычислить ее значение и присвоить переменной 1. Если формула не содержит ошибок, то следует вычислить значение подформулы в. Выбирается первый символ подформулы в, вычисляется значение и присваивается переменной l. После этого все готово для того, чтобы завершить вычисление значения всей формулы +АВ. В зависимости от знака операции выполняются соответствующие действия. Приведем программу, содержащую сценарий решения задачи (листинг 18.1).
Листинг 18.1. Вычисления значения формулы в префиксной нотации
<HTML>
<HEAD>
<TITLE>Вычисления значения формулы в префиксной нотации</TITLE>
<script language="JavaScript">
<!-- //
// Глобальные переменные
var st
var i
var с
var r
// Функция выбора для анализа очередного символа
function cursym()
{ i=i+l
var h
h = st.charAt(i);
return h
}
//Функция, определяющая, является ли символ знаком операции
function sig(z)
{ var p = ( Z ="+") || (z=="-") || (z=="*") || (z=="/"); return p}
// Функция обработки ошибки
function er (s )
{ var у = "ошибка в формуле: "+s+"<br>"
document.write (y)
}
// Значение формулы в префиксной нотации
function vform()
{ var g; var h; var 1; var r;
if (с >= "О" && с <= "9")
f g= c*l; return g }
else
{ if ( sig (c) == true)
{ h=c
с = cursym(); l = vforffl()
с = cursym () ; r =, vfom ()
switch (h)
{ case "+": g=l +r; break;
case "-": g= 1-r; break;
case "*": g= l*r; break;
case "/" : if (r != 0 ) { g= 1/r; break }
else er("Деление на ноль")
}
return g
}
else er("неверный символ")
}
}
// Функция, обеспечивающая начальные установки
//и вызов функции vform
function main (obj)
{ st = obj.f1.value
i=-1
с = cursym ()
r = vform()
obj.fres.value = r
}
//-—>
</script>
</HEAD>
<BODY>
<Н4>Вычисление значения формулы в префиксной нотации</Н4>
<FORM name="forml">
<pre>
Введите формулу: <input type="text" size=15 name="fl"><HR>
Значение формулы: <input type="text" size=15 name="fres"><HR>
</pre>
<input type="button" value=Bьшoлнить onClick="main(forml)">
<input type="reset" value=Очистить>
</FORM>
</BODY>
</HTML>
Представление формулы в обратной польской записи
При записи формулы в постфиксной нотации (обратной польской записи) знак операции ставится непосредственно после операндов. Например, формула а+b*с в постфиксной нотации: abc*+, формула (a+b)*c—(d+e)/k в обратной польской записи выглядит так: ab+c*de+k/—. Для формулы в инфиксной нотации вида А+В формула в постфиксной нотации имеет вид АВ+, где А и В — формулы в постфиксной нотации.
Напишем программу, которая по произвольной формуле в инфиксной нотации строит формулу в постфиксной нотации.
Формула состоит из переменных (представленных однобуквенными идентификаторами), знаков операций и круглых скобок. Допустимыми знаками операции являются знаки +, -, * и /. При просмотре формулы слева направо число открывающих скобок должно быть более или равно числу закрывающих. Во всей формуле число открывающих и закрывающих скобок должно быть одинаково. Формулу при решении задачи просмотрим слева направо один раз. Приведем метод решения, который получил название метода рекурсивного спуска.
Для решения задачи удобно ввести понятия, характеризующие отдельные части формулы и формулу целиком. Будем называть множителем либо переменную, либо формулу, заключенную в скобки. Будем называть термом — либо один множитель, либо последовательность множителей, соединенных знаками * или /. И, наконец, назовем формулой — один терм, либо последовательность термов, соединенных знаками + или -.
Сначала опишем функцию (назовем ее postform ), которая по формуле формирует обратную польскую запись. Формула состоит либо из одного терма, либо из последовательностей термов, соединенных знаком + или -. Если формула имеет вид Т1 + Т2— T3, то записанная в постфиксной нотации, она будет выглядеть так: T '1 T '2 + T '3, где T 'i - постфиксная нотация формулы T i (i = 1, 2, 3).
При написании функции postform будем использовать функцию postterm , которая "умеет" строить постфиксную нотацию для подформулы, определенной как терм. Пусть функция wrsym(h) помещает символ в строку результат. Как и ранее будем считать, что процедура cursym выбирает для анализа очередной символ.
Процедуру postform, которая строит по формуле в инфиксной нотации формулу в постфиксной нотации, можно записать следующим образом:
function postform()
{ postterm()
while ((с == "+") || (с == "-"))
{ var h=c
c=cursym()
postterm(}
wrsym(h)
}
}
Теперь следует описать функцию postterm . Вспомним, что терм состоит либо из одного множителя, либо из последовательности множителей, соединенных знаками *, /.
Если терм имеет вид M1 х M2 / M3 x M4, то записанный в постфиксной нотации он будет выглядеть так: M'1 M'2 x M' 3 / M' 4 x, где M' i - постфиксная нотация формулы Mi (i = 1, 2, 3, 4 ). При написании функции postterm можно использовать функцию postmn , которая "умеет" строить постфиксную нотацию для подформулы, определенной как множитель.
function postterm()
{ postmn()
while ((с == "*") || (с == "/"))
{ var h=c
c=cursym()
postmn()
wrsym(h)
}
}
Если множитель состоит лишь из переменной, то она уже находится в постфиксной нотации. Если множитель представляет собой формулу в скобках, т. е. имеет вид (F), то постфиксная нотация такой формулы совпадает с постфиксной нотацией формулы F. Для того чтобы построить постфиксную нотацию формулы F, следует обратиться к описанной ранее функции postform:
function postmn()
{ if((с >= "а") && (с <= "z"))
{ wrsym(c)
c=cursym()
}
else
{ if (с == "(" )
{ с = cursym()
postform{)
if (с != ")")
er=true
else
{ с = cursym() }
}
else er=true
}
}
Проследите, как будет осуществляться вызов описанных функций при преобразовании формулы, представленной на рис. 18.2.
Заметим, что функция postform содержит вызов функции postterm , которая обращается к функции postmn, последняя, в свою очередь, содержит вызов функции postform . Такую рекурсию иногда называют косвенной.
После того как пользователь ввел формулу и нажал на кнопку
Выполнить,
происходит вызов функции main, в которой выполняются необходимые начальные действия, такие как выбор первого символа для анализа, присвоение значения false переменной ег, чтобы отследить ситуацию, если в формуле содержится ошибка. В функции main осуществляется вызов функции postform о, и анализ ситуации после завершения работы этой функции.
|
| Рис 18.2. Построение постфиксной нотации HTML-код приведен в листинге 18.2. |
Листинг 18.2. Построение формулы в обратной польской записи
<HTML>
<HEAD>
<TITLE>Построение формулы в обратной польской записи</TITLE>
<script language="JavaScript">
<!-—
// Глобальные переменные
var s // Формула в обратной польской записи
var st // Исходная формула в инфиксной нотации
var i // Индекс очередного анализируемого символа
var er // Ошибка
var с // Очередной символ формулы
// Функция, осуществляющая начальные установки и
// вызов основной функции, осуществляющей построение
// обратной польской записи для формулы
function main(obj)
{ s=""
st=obj.f1.value
i=-l
er=false
c=cursym()
postform()
if (er)
alert ("Ошибка при задании формулы","<br>")
else
{ forml.fres.value=s }
}
// Выбор очередного символа
function cursym()
{ i=i+1
return st.charAt(i);
}
// Формирование строки, представляющей формулу
//в обратной польской записи
function wrsym(h)
{ s+=h }
// Обратная польская запись для формулы
function postform()
{ postterm()
while ((с == "+") || (c == "-"))
{ var h=c
c=cursym()
postterm()
wrsym(h)
}
}
// Обратная польская запись для терма
function postterm()
{ postmn()
while ((с == "*") || (с == "/"))
{ var h=c
c=cursym()
postmn()
wrsym(h) }
}
// Обратная польская запись для множителя
function postmn()
{ if ((с >= "a") && ( с <= "z"))
{ wrsym (с)
с = cursym ();
}
else { if (с == "(" )
{ с = cursym()
postform()
if (c != ")") -er= true
else
{ с = cursym() }
}
else er = true
}
}
//—->
</script>
</HEAD>
<BODY>
<Н4>Построение обратной польской записи методом
рекурсивного спуска</Н4>
<FORM name="form1">
<pre>
Введите формулу: <input type="text" size=25 name="fl"><HR>
Формула в постфиксной нотации: <input type="text" size=25 name="fres"><HR>
</pre>
<input type="button" value=Выполнить onClick=" main (form1)">
<input type="reset" value=Очистить><HR>
</FORM>
</BODY>
</HTML>
Если формула содержит ошибку (либо два операнда располагаются друг за другом, либо подряд следуют два знака, либо встретился недопустимый символ и др.), то значение переменной ег станет равным true. После завершения работы функции postformo проверяется значение переменной ег. Результат работы сценария в случае, когда формула содержит ошибку, представлена на рис 18.3.
Может возникнуть ситуация, когда проанализирована не вся формула, поэтому после работы функции postformo надо убедиться, что формула просмотрена целиком. Изменить сценарий, чтобы учесть такой случай, читателю предлагается в качестве упражнения.
Рис. 18.3.
Обработка ошибки
Вычисление значения формулы в прямой польской записи
Напишем сценарий, вычисляющий значение формулы. Формула состоит из целочисленных констант (от 0 до 9), знаков операций и круглых скобок. Допустимыми операциями являются сложение, вычитание, умножение и деление. Формулу при решении задачи требуется просмотреть слева направо один раз.
Для решения задачи удобно использовать понятия формулы, терма и множителя, введенные при решении предыдущей задачи.
Как и ранее, будем считать, что функция cursym () выдает для анализа текущий символ. Опишем функцию vaiform() , которая анализирует формулу, и, если формула построена правильно, вычисляет ее значение. По данному определению формула всегда начинается с терма. Будем считать, что функция vaiterm() вычисляет значение для части формулы, которую мы определили как терм. После вызова функции vaiterm() будет вычислено значение первого терма. Если далее в формуле следует знак + или знак -, то за знаком в формуле должен опять следовать терм. Вычислим значение и этого терма, воспользовавшись процедурой vaiterm() . Далее можно определить значение подформулы с двумя термами. Процесс продолжается до тех пор, пока после анализа очередного терма текущий символ не станет отличным от знака + или знака -.
Полностью функцию vaiform можно описать так:
function vaiform()
{ var t1 = vaiterm()
var t2
while ((c == "+"} || (c == "-"))
{ var h = с
с =cursym()
t2 = valterm()
if (h=="+") t1 = t1 + t2
else t1= t1 - t2
}
return Number(tl)
}
Напомним, что при вычислении значения формулы мы воспользовались функцией вычисления значения терма. Опишем ее. Мы предполагали, что терм состоит либо из одного множителя, либо из множителей, соединенных знаками умножения и деления. Поступим так, как уже поступали ранее. Будем считать, что функция vaimn () вычисляет значение формулы, определенной как множитель. Для того чтобы вычислить значение терма, следует сначала определить значение множителя. Анализируя знак операции, следующий за первым термом, мы либо прекращаем анализ формулы, либо вычисляем значение очередного множителя и т.д. Функция vaiterm() очень похожа на функцию valform() . Следует обратить внимание на значение делителя при выполнении операции деления.
function valterm()
{ var t1 = valmn()
var t2
while (c == "*")
{ var h = с
с = cursym()
t2 = valmn()
t1 = t1 * t2
}
return Number(t1)
}
Теперь необходимо описать функцию valmn () . Множителем может быть константа (ее значение нам известно) или формула в скобках (то есть множитель может иметь вид (F)). Если же очередной символ не является ни числом, ни открывающей скобкой, то формула содержит ошибку. Рассмотрим случай, когда множителем является формула в скобках. Значение формулы (F) совпадает со значением формулы F, а значение формулы мы уже умеем вычислять с помощью функции valformo, которой мы и воспользуемся. После вычисления значения формулы F очередным символом должна быть закрывающая скобка. Если это не так, то нарушен баланс скобок и формула содержит ошибку.
Будем, как и ранее, использовать логическую переменную ег, значение которой изменится на true в случае определения ошибки в формуле. Приведем описание функции valmn () :
function valmn()
{ if ((с >= "1") && ( с <= "9"))
{ var h=Number(c)
с = cursym();
return h
}
else
{ if (c == "(")
{ с = cursym()
var t = valform()
if (c != ")") er= true
else
{ с = cursym (); return Number(t) }
}
else er = true
}
}
Заметим, что функция vaiform содержит вызов функции vaiterm , которая содержит вызов функции valmn , последняя, в свою очередь, обращается к функции vaiform . Здесь, как и в предыдущем случае, имеет место косвенная рекурсия.
Напомним, что рассмотренная нами ранее функция evai(s) рассматривает строку s как выражение, и вычисляет ее значение.
В программе для контроля работы описанных функций используется функция vaitest , которая обращается к функции eval и записывает в соответствующее поле формы вычисленное с ее помощью значение (рис. 18.4).
Функция eval обладает большими возможностями, чем приведенная программа. В этом смысле программа носит демонстрационный характер. Но если в формуле присутствуют знаки операций, не определенные в языке JavaScript, то воспользоваться методом; eval не удается, требуется писать свою программу определения значения формулы. Предложенный метод рекурсивного спуска оказывается полезным при решении многих задач.
|
| Рис 18.4. Значение формулы в инфиксной нотации Приведем полностью программу, решающую задачу (листинг 18.3). |
Листинг 18.3. Вычисление значения формулы в инфиксной нотации
<HTML>
<HEAD>
<TITLE>Задача вычисления значения формулы</TITLE>
<script language="JavaScript">
<!-- //
var st // Исходная формула
var i // Индекс текущего символа
var er // Фиксация ошибки
var с // Очередной символ формулы
// Выбор очередного символа
function cursym()
{ i=i+l; return st.charAt(i)}
// Значение формулы
function valform()
{ var t1 = valterm()
var t2
while ( (c == "+") || (c == "-"))
{ var h = с
с =cursym()
t2 = valterm()
if (h=="+") tl = tl + t2
else tl= tl - t2
}
return Number(tl)
}
// Значение терма
function valterm()
( var tl = valmn()
var t2
while (c == "*")
{ var h =c
с = cursym()
t2 = valmn()
tl = tl * t2
}
return Number(tl)
}
// Значение множителя
function valmn()
{ if ((c >= "1") && (c <= "9"))
{ var h= Number(c)
с = cursym();
return Number(h)
}
else
{ if (c == "(")
{ с = cursym()
var t = valform()
if (c != ")") er= true
else { с = cursym (); return Number(t)}
}
else er = true
}
}
// Установка начальных значений и вызов функции vform
function main(obj)
{ st = obj.f1.value
i=-1
er = false
с = cursym()
r = valform()
if (er || (i != st.length))
alert ("Ошибка при задании формулы","<br>")
else obj.fres.value = r
}
// Проверка работы описанных функций с помощью функции eyal
function testval (obj)
{ st = obj.fLvalue
r= eval(st)
obj.test.value = r
if (er)
alert ("Ошибка при задании формулы","<br>")
else
{ obj.test.value = r }
}
//-—>
</script>
</HEAD>
<BODY>
<Р>Вычисление значения формулы методом рекурсивного спуска</Р>
<рrе>
<FORM name="form1">
Введите формулу: <input type="text" size=30 name="fl"><HR>
Значение формулы: <input type="text" size=30 name="fres"><HR>
<input type="button" value=Выполнить onClick="main(form1)"><HR>
Функция eval: <input type="text" size=30 name="test"><HR>
<input type="button" value=Проверка onClick="testval(form1)"><HR>
<input type="reset" value=Очистить ><HR>
</FORM>
</pre>
</BODY>
</HTML>
Расчет сопротивления параллельно-последовательной схемы
Применим метод рекурсивного спуска для решения следующей задачи. К наиболее простым и часто встречающимся типам соединения проводников относятся последовательное и параллельное соединения. При последовательном соединении электрическая цепь не имеет разветвлений, все проводники включают в цепь поочередно друг за другом. На рис. 18.4 показано последовательное соединение двух проводников, имеющих сопротивление R1 и R2. Полное сопротивление R при последовательном соединении определяется следующим образом:
R = R1 + R2.
Аналогичную формулу можно вывести для любого числа последовательно соединенных проводников.
|
| Рис 18.4. Последовательное соединение проводников |
На рис. 18.5 показано параллельное соединение двух проводников с сопротивлениями R1 и R2. Величина, обратная полному сопротивлению участка, равна сумме величин, обратных сопротивлению отдельных проводников:
1/R = 1/R1 + 1/R2
|
| Рис 18.5. Параллельное соединение проводников |
Отсюда следует, что
R = (R1 x R2)/(R1 + R2).
Аналогичную формулу можно вывести для любого числа параллельно соединенных проводников.
Предположим, что задана электрическая схема из резисторов (сопротивлений). Схема является параллельно-последовательной (далее, ПП-схема), т. е. содержит только последовательные и параллельные соединения регистров.
Формально понятие ПП-схемы можно представить следующим образом:
R = 1/((1/R1)+ ... +(1/Rn)),
где R1, R2, ... , Rn — сопротивления параллельно соединенных схем. На рис. 18.6 иллюстрируется понятие ПП-схемы.
|
| Рис 18.6. Вычисление сопротивления ПП-схемы |
Напишем программу, которая определяет полное сопротивление параллельно-последовательной схемы. В последовательных и параллельных соединениях участвуют, по крайней мере, две схемы. Величины сопротивлений задаются целыми числами из диапазона [1; 9].
Изображение электрической схемы будем записывать по определенным правилам в виде строки символов. Если схема состоит из одного проводника, то задается число — величина сопротивления. Последовательное соединение схем будем задавать строкой вида (А1+А2+. . .+Аn) , где Ai — либо один проводник, либо электрическая схема. Параллельное соединение будем задавать строкой вида (А1*А2*... *Аn), где Ai — либо один проводник, либо электрическая схема.
Такую задачу мы можем решить методом рекурсивного спуска. Предположим, что мы написали функцию (назовем ее VF), которая обрабатывает последовательное соединение и вычисляет его сопротивление. Функция VF использует функцию VT, которая обрабатывает параллельное соединение и вычисляет для него значение сопротивления. Функция VT вызывает функцию VM, которая обрабатывает или схему из одного элемента, или произвольную схему. Так как в последовательных и параллельных соединениях участвуют, по крайней мере, два элемента, то описание схемы должно начинаться со скобки. HTML-код приведен в листинге 18.4.
Листинг 18.4. Задача вычисления сопротивления ПП-схемы
<HTML>
<HEAD>
<TITLE>Задача вычисления сопротивления ПП-схемы</TITLE>
<script language="JavaScript">
<!-- //
var с //Текущий символ анализируемой схемы
var r
var s // Заданная схема
var i
// Функция cursym выдает очередной символ схемы
function cursym()
{ i=i+l; return s.charAt(i)}
// Функция errform фиксирует ошибку
function errform (s)
{ document.writeln ('Ошибка при задании схемы: ',s) }
// Функция vF обрабатывает последовательно соединенную схему
//и выдает для нее значение сопротивления
function vF()
{ var x
var у
у = vT {) // Значение первого элемента схемы
while (с =='+')
{ с = cursym()
х = vT()
у = y+x
}
return у
}
// Функция vT обрабатывает параллельно соединенную схему
//и выдает для нее значение сопротивления
function vT()
{ var x; var у; var z;
z = vM()
у = 1/z // значение первого элемента схемы
while (с == '*')
{ с = cursym() x = vM(); у = у+1/х }
return (1/у)
}
// Функция vM обрабатывает схему из одного элемента
// или произвольную ПП-схему
function vM()
{ var x; var у; var r
var cp
if ((c >='!')&&(c<='9'))
{ r= 1*c
с = cursym()
}
else
{ if (c =='(')
{ с = cursym()
x = vM()
if (!((c =='+') || (c ='*')))
{ errform('Нет знака')}
else
( cp = с
с = cursym()
У = vF()
if ( C p == '+')
( r = x+y}
else
{ r= y/(y/x + 1)}
if ( с != ') ')
errform('HeT закрывающей скобки')
else
с = cursym()
}
}
else errform('Неверное начало схемы')
}
return r
}
// Инициализация глобальных.переменных и вызов основной функции
function main (obj)
{ s= obj.f.value
i = -1
с = cursym()
r = vF()
obj.fres.value = r
}
//-—>
</script>
</HEAD>
<BODY>
<Н4>Вычисление сопротивления ПП-схемы
методом рекурсивного спуска</Н4>
<рrе>
<FORM name="form1">
Введите формулу: <input type="text" size=30 name="f"><HR>
Значение формулы: <input type="text" size=30 name="fres"><HR>
<input type="button" value="Выполнить"
onClick="main(forml)"><HR>
<input type="reset" value=" Очистить "><HR>
</FORM>
</pre>
</BODY>
</HTML>
На рис. 18.7 приведен результат работы программы. Изобразите схему, которая
представлена строкой, и проверьте правильность работы программы.
|
| Рис 18.7. Пример работы сценария вычисления сопротивления заданной ПП-схемы |
1. Напишите функцию, которая по формуле, содержащей однобуквенные идентификаторы, круглые скобки, знаки операций сложения, вычитания, умножения, выясняет, правильно ли построена формула.
2. Напишите функцию, которая по формуле в префиксной нотации строит формулу в инфиксной нотации.
3. Напишите функцию, которая по формуле в постфиксной нотации строит формулу в инфиксной нотации.
4. Пусть формула строится из логических переменных, круглых скобок, логического отрицания, логического и, логического или. Напишите сценарий, который преобразует данную формулу в префиксную нотацию.
5. Пусть формула строится из логических переменных, круглых скобок, логического отрицания, логического и, логического или. Напишите сценарий, который преобразует данную формулу в постфиксную нотацию
| Назад | Содержание | Вперед |