Соответствующее математическое выражение с регулярным выражением?

Ответ 1

Совпадение парсеров с регулярным выражением вполне возможно.

Вот Perl script, который будет разбирать произвольные глубокие совпадающие парсеры. В то время как он выкидывает несогласованные parens снаружи, я не проектировал его специально для проверки parens. Он будет разбирать произвольно глубокие parens, пока они сбалансированы. Это поможет вам начать работу.

Ключ - это рекурсия как в регулярном выражении, так и в использовании. Играйте с ним, и я уверен, что вы можете получить это, чтобы также отметить несовпадающие пены. Я думаю, что если вы поймете, что это регулярное выражение выбрасывает и подсчитывает parens (т.е. Тестирует нечетные parens в тексте, не совпадающем с текстом), у вас есть неверные, неуравновешенные parens.

#!/usr/bin/perl
$re = qr  /
     (                      # start capture buffer 1
        \(                  #   match an opening paren
        (                   # capture buffer 2
        (?:                 #   match one of:
            (?>             #     don't backtrack over the inside of this group
                [^()]+    #       one or more 
            )               #     end non backtracking group
        |                   #     ... or ...
            (?1)            #     recurse to opening 1 and try it again
        )*                  #   0 or more times.
        )                   # end of buffer 2
        \)                  #   match a closing paren
     )                      # end capture buffer one
    /x;


sub strip {
    my ($str) = @_;
    while ($str=~/$re/g) {
        $match=$1; $striped=$2;
        print "$match\n";
        strip($striped) if $striped=~/\(/;
        return $striped;
    }
}

while(<DATA>) {
    print "start pattern: $_";
    while (/$re/g) { 
        strip($1) ;
    }
}   

__DATA__
"(apple + (-0.5)) * (boy - 1)"
"((((one)two)three)four)x(one(two(three(four))))"
"a) * (b + c) / (d"
"-a * (b / 1.50)"

Вывод:

start pattern: "(apple + (-0.5)) * (boy - 1)"
(apple + (-0.5))
(-0.5)
(boy - 1)
start pattern: "((((one)two)three)four)x(one(two(three(four))))"
((((one)two)three)four)
(((one)two)three)
((one)two)
(one)
(one(two(three(four))))
(two(three(four)))
(three(four))
(four)
start pattern: "a) * (b + c) / (d"
(b + c)
start pattern: "-a * (b / 1.50)"
(b / 1.50)

Ответ 2

Регулярные выражения могут использоваться только для распознавания обычных языков. Язык математических выражений не является регулярным; для этого вам понадобится реализовать фактический парсер (например, LR).

Ответ 3

Используйте автомат pushdown для сопоставления paranthesis http://en.wikipedia.org/wiki/Pushdown_automaton (или просто стек;-))

Подробности для решения стека:

while (chr available)
    if chr == '(' then
      push '('
    else
      if chr == ')' then
        if stack.elements == 0 then
          print('too many or misplaced )')
          exit
        else
          pop //from stack
end while
if (stack.elements != 0)
  print('too many or misplaced(')

Даже просто: просто держите счетчик вместо стека.

Ответ 4

Я считаю, что вам будет лучше реализовать настоящий парсер, чтобы выполнить то, что вам нужно.

Парсер простых математических выражений - "Анализ 101", и есть несколько примеров, которые можно найти в Интернете.

Некоторые примеры включают:

• ANTLR: Пример оценки экспрессии (ANTLR-грамматики могут ориентироваться на несколько языков)
• pyparsing: http://pyparsing.wikispaces.com/file/view/fourFn.py (pyparsing - это библиотека Python)
• Lex и Yacc: http://epaperpress.com/lexandyacc/ (содержит учебник PDF и пример кода для калькулятора).

Обратите внимание, что грамматика, необходимая для проверки выражений, проще, чем приведенные выше примеры, поскольку примеры также реализуют оценку выражения.

Ответ 5

Вы не можете использовать регулярное выражение для выполнения действий, подобных скобкам баланса.

Ответ 6

Это сложно с одним регулярным выражением, но довольно просто с использованием смешанного регулярного выражения/процедурного подхода. Идея состоит в том, чтобы создать регулярное выражение для простого выражения (без круглых скобок), а затем повторно заменить ( simple-expression ) на некоторую атомную строку (например, идентификатор). Если конечное сокращенное выражение соответствует одному и тому же "простому" шаблону, исходное выражение считается действительным.

Иллюстрация (в php).

function check_syntax($str) {

    // define the grammar
    $number = "\d+(\.\d+)?";
    $ident  = "[a-z]\w*";
    $atom   = "[+-]?($number|$ident)";
    $op     = "[+*/-]";
    $sexpr  = "$atom($op$atom)*"; // simple expression

    // step1. remove whitespace
    $str = preg_replace('~\s+~', '', $str);

    // step2. repeatedly replace parenthetic expressions with 'x'
    $par = "~\($sexpr\)~";
    while(preg_match($par, $str))
        $str = preg_replace($par, 'x', $str);

    // step3. no more parens, the string must be simple expression
    return preg_match("~^$sexpr$~", $str);
}


$tests = array(
    "a * b + c",
    "-a * (b / 1.50)",
    "(apple + (-0.5)) * (boy - 1)",
    "--a *+ b @ 1.5.0",
    "-a * b + 1)",
    "a) * (b + c) / (d",
);

foreach($tests as $t)
    echo $t, "=", check_syntax($t) ? "ok" : "nope", "\n";

Вышеупомянутый только подтверждает синтаксис, но тот же метод можно также использовать для построения реального парсера.

Ответ 7

Для сопоставления скобок и реализации других правил проверки выражений, вероятно, проще всего написать собственный небольшой парсер. Регулярные выражения не подходят для такого рода ситуаций.

Ответ 8

Хорошо, моя версия скобки в ActionScript3, используя этот подход, дает много усилий для анализа части перед скобкой, внутри скобок и после парентита, если некоторые скобки остаются в конце, вы можете поднять предупреждение или отказаться от отправки в окончательную функцию eval.

package {
import flash.display.Sprite;
import mx.utils.StringUtil;
public class Stackoverflow_As3RegexpExample extends Sprite
{
    private var tokenChain:String = "2+(3-4*(4/6))-9(82+-21)"
    //Constructor
    public function Stackoverflow_As3RegexpExample() {
        // remove the "\" that just escape the following "\" if you want to test outside of flash compiler.
        var getGroup:RegExp = new RegExp("((?:[^\\(\\)]+)?)   (?:\\()       (  (?:[^\\(\\)]+)? )    (?:\\))        ((?:[^\\(\\)]+)?)", "ix")   //removed g flag
        while (true) {
            tokenChain = replace(tokenChain,getGroup)
            if (tokenChain.search(getGroup) == -1) break; 
        }
        trace("cummulativeEvaluable="+cummulativeEvaluable)
    }
    private var cummulativeEvaluable:Array = new Array()
    protected function analyseGrammar(matchedSubstring:String, capturedMatch1:String, capturedMatch2:String,  capturedMatch3:String, index:int, str:String):String {
        trace("\nanalyseGrammar str:\t\t\t\t'"+str+"'")
        trace("analyseGrammar matchedSubstring:'"+matchedSubstring+"'")
        trace("analyseGrammar capturedMatchs:\t'"+capturedMatch1+"'  '("+capturedMatch2+")'   '"+capturedMatch3+"'")
        trace("analyseGrammar index:\t\t\t'"+index+"'") 
        var blank:String = buildBlank(matchedSubstring.length)
        cummulativeEvaluable.push(StringUtil.trim(matchedSubstring))
        // I could do soo much rigth here!
        return str.substr(0,index)+blank+str.substr(index+matchedSubstring.length,str.length-1)
    }
    private function replace(str:String,regExp:RegExp):String {
        var result:Object = regExp.exec(str)
        if (result)
            return analyseGrammar.apply(null,objectToArray(result)) 
        return str
    }
    private function objectToArray(value:Object):Array {
        var array:Array = new Array()
        var i:int = 0
        while (true) {
            if (value.hasOwnProperty(i.toString())) {
                array.push(value[i])
            } else {
                break;
            }
            i++
        }
        array.push(value.index)
        array.push(value.input)
        return array
    }
    protected function buildBlank(length:uint):String {
        var blank:String = ""
        while (blank.length != length)
            blank = blank+" "
        return blank
    }
}

}

Он должен проследить это:

analyseGrammar str:             '2+(3-4*(4/6))-9(82+-21)'
analyseGrammar matchedSubstring:'3-4*(4/6)'
analyseGrammar capturedMatchs:  '3-4*'  '(4/6)'   ''
analyseGrammar index:           '3'

analyseGrammar str:             '2+(         )-9(82+-21)'
analyseGrammar matchedSubstring:'2+(         )-9'
analyseGrammar capturedMatchs:  '2+'  '(         )'   '-9'
analyseGrammar index:           '0'

analyseGrammar str:             '               (82+-21)'
analyseGrammar matchedSubstring:'               (82+-21)'
analyseGrammar capturedMatchs:  '               '  '(82+-21)'   ''
analyseGrammar index:           '0'
cummulativeEvaluable=3-4*(4/6),2+(         )-9,(82+-21)