Code: Select all
;~ Test (раскомментируйте одно из математических выражений и обе строки с MsgBox)
;~ --------------------------------------------------------------------------------------
;~ x = (-1 - (2 + 4) - 5) * 6 ; -72
;~ x = sin(cos(1)) ; 0.514395
;~ x = - 2 ** - 3 ; -0/125
;~ x = 1 > 1 + - 1 ; 1
;~ x = - 1 - ! 1 + - 1 ; -2
;~ x = - 2 * - 3 ; 6
;~ x = 2 + - 3 ; -1
;~ x = - 5 // - 2 ; 2
;~ x = Mod(- 5, - 2) ; -1
;~ x = max(1, min(2, - 3), - 4) ; 1
;~ x = Round(- 1 / 3, 2) ; 0.33
;~ x = - 1 + ! - 0 ; 0
;~ x = 1 && -1 ; 1
;~ x = 1 = 1 || 2 <> -2 ; 1
;~ a := "2", b := "3", x := "a / b + b / a" ; 2.166667
;~ a := "-2", x := "a ** 3" ; -8
;~ a := "- 2", x := "2 ** a" ; 0.25
;~ @ := "- 8", # := "- 4", $ := "2", x := "@ / # / $" ; 1
;~ x = 2**3**2 ; 512 Эквивалентно 2**(3**2)
;~ x = !!-5 ; 1
;~ x = 2**!0 ; 2
;~ x = ----1 ; 1
;~ x = -!-!-!0 ; -1
;~ MsgBox % ToPostfix(x)
;~ MsgBox % _Evaluate(x)
/* -----------------------------------------------------------------------------------------------------------------
* Основная функция расширенного алгоритма Дейкстра. Преобразует обычное математическое выражение infixExpr в
* обратную польскую запись postfixExpr.
* ------------------------------------------------------------------------------------------------------------------
*/
ToPostfix(infixExpr) {
;~ Предварительная обработка математического выражения:
;~ 1. Косметическая замена буквенных логических операторов Not, And, Or их символьными обозначениями.
infixExpr := RegExReplace(infixExpr, "i)\bNot\b", "!")
infixExpr := RegExReplace(infixExpr, "i)\bAnd\b", "&&")
infixExpr := RegExReplace(infixExpr, "i)\bOr\b", "||")
;~ 2. Удаление всех унарных плюсов и переобозначение унарных минусов символами ~ и ¬. Разделение унарных минусов на
;~ два класса делается для того, чтобы сохранить основное правило алгоритма Дейкстра об извлечении операторов из
;~ стека. Унарные минусы из этих классов отличаются друг от друга только приоритетом. Первые имеют самый высокий
;~ приоритет, а вторые по приоритету совпадают с обычным минусом (см. ниже "Приритет операторов"). Унарные минусы из
;~ первого класса непосредственно следуют за каким-либо оператором, а из второго класса расположены или в начале
;~ выражения, или непосредственно после открывающей скобки, или в начале параметра функции. Это отражено ниже в
;~ регулярных выражениях оператора RegExReplace(), заменяющих унарные минусы символами ~ и ¬ соответстветственно
;~ принадлежности к первому или второму классу. Например, выражение -2**-3, эквивалентное выражению -(2**(-3)),
;~ после переобозначения принимает вид ¬2**~3.
;~ Унарные плюсы полностью удаляются из выражения. Если этого не сделать, то подобно унарным минусам их также
;~ потребуется разделить на два класса.
infixExpr := RegExReplace(infixExpr, "(?<=^|[(*/+!&|-])\s*\+")
infixExpr := RegExReplace(infixExpr, "(?<=[*/+!&|-])\s*-", "~")
infixExpr := RegExReplace(infixExpr, "(?<=^|[(,])\s*-", "¬")
_SciTE_Output(">>>>> Line " A_LineNumber ", ErrorLevel = " ErrorLevel ", infixExpr =`r`n" infixExpr)
;~ Приоритет операторов
priority := {"(": 0, ">=": 1, ">": 1, "=": 1, "!=": 1, "<>": 1, "<": 1, "<=": 1, "||": 2, "&&": 3, "+": 4, "¬": 4
, "-": 4, "*": 5, "/": 5 , "//": 5, "**": 6, "!": 7, "~": 7}
stack := []
postfixExpr =
pos := 0
;~ Посимвольное считывание строки infixExpr.
while (pos < StrLen(infixExpr)) {
pos += 1
symbol := SubStr(infixExpr, pos, 1)
;~ Если символ является цифрой, буквой или одним из символов: _, ., @, # и $, то находится все слово word,
;~ состоящее из таких символов и начинающееся в позиции pos.
if IsCharacter(symbol) {
word := GetWord(infixExpr, pos)
;~ В соответствии с алгоритмом Дейкстра: если word - число, то оно присоединяется к строке postfixExpr.
;~ Дополнительно к алгоритму Дейкстра:
;~ Если word - имя функции, то оно отправляется в стек.
;~ Если word - пользовательская переменная, то вычисляется ее значение, модуль которого присоединяется к
;~ строке postfixExpr, а знак, если он отрицательный, помещается в стек.
if IsNumber(word)
postfixExpr .= word " "
else if IsFunction(word) {
stack.Push(word)
} else {
;~ В этом случае word - имя переменной.
value := %word%
value := StrReplace(value, " ", "")
postfixExpr .= Abs(value) " "
If (value < 0)
stack.Push("~")
}
}
;~ Основная часть алгоритма Дейкстра: если символ является оператором, то он переносится в стек. Предварительно
;~ в зависимости от соотношения приоритетов предыдущие операторы извлекаются из стека и присоединяются к
;~ строке postfixExpr. Причем правоассоциативные операторы (**, ~ и !) обрабатываются отдельно. Отличие только в
;~ неравенстве: >= заменено на >.
else if IsOperator(symbol) {
operator := GetOperator(infixExpr, pos)
If IsLeftAssoc(operator) ; Левоассоциативные
while (stack.Length() > 0 && priority[Peek(stack)] >= priority[operator])
postfixExpr .= stack.Pop() " "
else ; Правоассоциативные
while (stack.Length() > 0 && priority[Peek(stack)] > priority[operator])
postfixExpr .= stack.Pop() " "
stack.Push(operator)
}
else if (symbol = "(") {
;~ Согласно алгоритму Дейкстра открывающая скобка помещается в стек.
;~ Дополнительно к алгоритму Дейкстра. Если на вершине стека имя функции, то - это функциональная скобка, и
;~ за ней в исходной строке infixExpr следуют параметры функции. Чтобы отметить это, в строку postfixExpr
;~ помещается якорь - одиночная кавычка '. Таким образом параметры функции в строке postfixExpr будут
;~ заключены между кавычкой и (см. следующий блок операторов) именем применяемой к ним функции.
if IsFunction(Peek(stack)) ; Peek(stack) - вершина стека.
postfixExpr .= "' "
stack.Push(symbol)
}
else if (symbol = ")") {
;~ Согласно алгоритму Дейкстра все операторы от вершины стека до открывающей скобки удаляются из стека и
;~ присоединяются к строке postfixExpr. Открывающая скобка удаляется из стека.
;~ Дополнительно к алгоритму Дейкстра, если вершина стека - имя функции, то оно также присоединяется к
;~ строке postfixExpr.
while (Peek(stack) != "(")
postfixExpr .= stack.Pop() " "
stack.Pop()
if IsFunction(Peek(stack))
postfixExpr .= stack.Pop() " "
}
else if (symbol = ",") {
;~ Запятая, разделяющая параметры функции, действует аналогично закрывающей скобке.
while Peek(stack) != "("
postfixExpr .= stack.Pop() " "
}
}
;~ В соответствии с алгоритмом Дейкстра операторы, оставшиеся после завершения прохода строки infixExpr,
;~ переносятся из стека в postfixExpr.
loop % stack.Length()
postfixExpr .= stack.Pop() " "
return postfixExpr
}
/* -----------------------------------------------------------------------------------------------------------------
* Функция вычисляет математическое выражение mathExpr с помощью обратной польской записи postfixExpr
* ------------------------------------------------------------------------------------------------------------------
*/
_Evaluate(mathExpr) {
postfixExpr := ToPostfix(mathExpr)
stack := []
pos := 0
;~ Получение по одному символов из postfixExpr.
while (pos < StrLen(postfixExpr)) {
pos += 1
symbol := SubStr(postfixExpr, pos, 1)
;~ Проверяется, что символ является обозначением оператора или его частью. В последнем случае находится
;~ весь оператор. Далее согласно алгоритму Дейкстра из стека выгружаются операнды (для унарных операторов
;~ один операнд), и выполняется соответствующее действие. Результат помещается в стек.
if IsOperator(symbol) {
operator := GetOperator(postfixExpr, pos)
param2 := stack.Pop()
if Not IsUnary(symbol)
param1 := stack.Pop()
stack.Push(Execute(operator, param1, param2))
;~ Кавычка, после которой в строке postfixExpr находятся параметры функции, переносится в стек.
} else if (symbol = "'")
stack.Push("'")
else if IsCharacter(symbol) {
word := GetWord(postfixExpr, pos)
;~ Число отправляется в стек.
if IsNumber(word) {
stack.Push(word)
} else {
;~ word в этом случае - имя функции. Ее параметры выгружаются из стека в массив params, пока в стеке
;~ не будет достигнута метка '. Метка после этого удаляется.
params := []
while Peek(stack) != "'"
params[A_Index] := stack.Pop()
stack.Pop()
;~ Порядок параметров в массиве params меняется на противоположный.
params := Revers(params)
;~ Пользуемся тем, что все функции в AutoHotkey принимают параметры, упакованные в массив:
stack.Push(%word%(params*))
}
}
}
return stack.Pop()
}
;~ ----------------------------------------------------------------------------------------------------
;~ Вспомогательные функции
;~ ----------------------------------------------------------------------------------------------------
;~ Если строка состоит из одного символа, то функция проверяет, является ли символ оператором или хотя бы его частью.
;~ Если строка состоит из двух символов, то функция проверяет, является ли строка оператором.
IsOperator(string) {
return string ~= "^(?:\>=|\>|=|!=|\<\>|\<|\<=|\||\|\||&|&&|\+|-|¬|\*|/|//|\*\*|!|~)$"
}
;~ Функция прверяет, является ли word именем математической функции из перечисленных ниже.
IsFunction(word) {
return word ~= "i)^(?:Abs|Ceil|Log|Ln|Exp|Floor|ASin|ACos|ATan|Sin|Cos|Tan|Sqrt|Min|Max|Mod|Round)$"
}
;~ Функция проверяет, является ли символ цифрой, буквой, подчеркиванием или точкой. А также специально для AutoHotkey
;~ еще одним из разрешенных символов @, #, $.
IsCharacter(symbol) {
return symbol ~= "[\w.@#$]"
}
;~ Функция проверяет, является ли оператор унарным.
IsUnary(operator) {
return operator ~= "^[!~¬]$"
}
;~ Функция проверяет, является ли word десятичным числом.
IsNumber(word) {
return word ~= "^\d*\.?\d*$"
}
;~ Функция меняет нумерацию в массиве array на противоположную.
Revers(array) {
revArray := []
length := array.Length()
loop % length
revArray[A_Index] := array[length - A_Index + 1]
return revArray
}
;~ Функция возвращает вершину стека.
Peek(stack) {
return stack[stack.Length()]
}
;~ Функция возвращает число, имя функции или переменной, начинающиеся в выражении expression с позиции pos.
GetWord(expression, ByRef pos) {
word =
while pos <= StrLen(expression) {
symbol := SubStr(expression, pos, 1)
if IsCharacter(symbol) {
word .= symbol
pos += 1
}else{
pos -= 1
break
}
}
return word
}
;~ Функция возвращает оператор, начинающийся в выражении expression с позиции pos.
GetOperator(expression, ByRef pos) {
firstSymbol := SubStr(expression, pos, 1)
secondSymbol := SubStr(expression, pos + 1, 1)
if IsOperator(firstSymbol secondSymbol) {
pos += 1
return firstSymbol secondSymbol
} else
return firstSymbol
}
;~ Функция проверяет, является ли оператор левоассоциативным
IsLeftAssoc(operator) {
return Not operator ~= "^(\*\*|!|~)$"
}
;~ Функция выполняет действия для различных математических операторов.
Execute(operator, first, second) {
switch operator {
case "||": return first || second
case "&&": return first && second
case ">=": return first >= second
case ">": return first > second
case "=": return first = second
case "!=": return first != second
case "<>": return first != second
case "<": return first < second
case "<=": return first <= second
case "+": return first + second
case "-": return first - second
case "*": return first * second
case "/": return first / second
case "//": return first // second
case "**": return first ** second
case "!": return ! second
case "~": return - second
case "¬": return - second
}
}
