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

Question

Например, это допустимые математические выражения:

a * b + c
-a * (b / 1.50)
(apple + (-0.5)) * (boy - 1)

И это недопустимые математические выражения:

--a *+ b @ 1.5.0  // two consecutive signs, two consecutive operators, invalid operator, invalid number
-a * b + 1)  // unmatched parentheses
a) * (b + c) / (d  // unmatched parentheses

У меня нет проблем с сопоставлением чисел с плавающей точкой, но у меня возникают проблемы ссоответствие скобок.Любая идея?Если есть лучшее решение, чем регулярное выражение, я тоже приму.Но регулярное выражение предпочтительнее.

========

Редактировать:

Я хочу прокомментировать мой выбор «принятого ответа», надеясьчто люди с таким же вопросом и найдут эту ветку не будут введены в заблуждение.

Есть несколько ответов, которые я считаю «принятыми», но я не знаю, какой из них лучший.Поэтому я выбрал принятый ответ (почти) случайным образом.Я рекомендую прочитать ответ Гийома Маларта, а также принятый ответ.Все они дают практические решения моего вопроса.Для несколько строгого / теоретического ответа, пожалуйста, прочитайте комментарии Дэвида Торнли под принятым ответом.Как он упомянул, расширение Perl регулярным выражением (происходящим из регулярного языка) делает его «нерегулярным».(Я не упомянул ни одного языка в своем вопросе, поэтому большинство ответчиков предположили реализацию регулярных выражений в Perl - вероятно, наиболее популярную реализацию. Я так и сделал, когда отправил свой вопрос.)

Пожалуйста, исправьте меня, если я сказал что-то не таквыше.

Answer 1

Используйте автомат для сопоставления парантеза 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(')

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

#!/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)

Answer 5

Это сложно с одним регулярным выражением, но довольно легко с использованием смешанного регулярного выражения / процедурного подхода.Идея состоит в том, чтобы создать регулярное выражение для простого выражения (без скобок), а затем многократно заменить ( 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";

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

Answer 6

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

Answer 7

Хорошо, вот моя версия поиска скобок в 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)

Answer 8

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