Last active
August 21, 2018 23:53
-
-
Save vincentdchan/78435adcbb007df77e0c674201202925 to your computer and use it in GitHub Desktop.
parsing math expression
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace CalHomework | |
{ | |
/// <summary> | |
/// Everything according to my blog: | |
/// https://vincentdchan.github.io/2016/07/parse-math-expression/ | |
/// </summary> | |
class ExpresssionParser | |
{ | |
Dictionary<char, int> OperatorsPrecedence = new Dictionary<char, int>() | |
{ | |
{'+', 1}, | |
{'-', 1}, | |
{'*', 2}, | |
{'/', 2}, | |
}; | |
private Stack<int> valueStack = new Stack<int>(); | |
private Stack<char> operatorStack = new Stack<char>(); | |
private string content; | |
private int ptr = 0; | |
public int Parse(string _content) | |
{ | |
content = _content; | |
return Parse(); | |
} | |
private bool isDigit(char ch) | |
{ | |
return ch >= '0' && ch <= '9'; | |
} | |
private bool isOp(char ch) | |
{ | |
return ch == '+' || ch == '-' || ch == '*' || ch == '/'; | |
} | |
private string readToken() | |
{ | |
StringBuilder sb = new StringBuilder(); | |
if (!isDigit(content[ptr])) | |
{ | |
throw new ParseException(); | |
} | |
char ch; | |
while (ptr < content.Length && isDigit(ch = content[ptr])) | |
{ | |
sb.Append(ch); | |
ptr++; | |
} | |
return sb.ToString(); | |
} | |
private void reduce() | |
{ | |
var a = valueStack.Pop(); | |
var b = valueStack.Pop(); | |
var _op = operatorStack.Pop(); | |
valueStack.Push(reduce(a, b, _op)); | |
} | |
private char readOperator() | |
{ | |
StringBuilder sb = new StringBuilder(); | |
if (!isOp(content[ptr])) | |
{ | |
throw new ParseException(); | |
} | |
else | |
{ | |
return content[ptr++]; | |
} | |
} | |
private int reduce(int a, int b, char op) | |
{ | |
switch(op) | |
{ | |
case '+': | |
return a + b; | |
case '-': | |
return a - b; | |
case '*': | |
return a * b; | |
case '/': | |
return a / b; | |
default: | |
throw new ParseException(); | |
} | |
} | |
private bool isFinished() | |
{ | |
return ptr < content.Length; | |
} | |
private int Parse() | |
{ | |
// init | |
valueStack.Push(int.Parse(readToken())); | |
while (isFinished()) | |
{ | |
var op = readOperator(); | |
if (operatorStack.Count == 0) | |
{ | |
operatorStack.Push(op); | |
valueStack.Push(int.Parse(readToken())); | |
} | |
else | |
{ | |
bool isReduced = false; | |
while (operatorStack.Count > 0) | |
{ | |
var opTop = operatorStack.Peek(); | |
if (OperatorsPrecedence[op] > OperatorsPrecedence[opTop]) | |
{ | |
operatorStack.Push(op); | |
valueStack.Push(int.Parse(readToken())); | |
isReduced = false; | |
break; | |
} else | |
{ | |
reduce(); | |
isReduced = true; | |
} | |
} | |
if (isReduced) | |
{ | |
ptr--; | |
} | |
} | |
} | |
// reduce until finished | |
while (valueStack.Count > 1) | |
{ | |
reduce(); | |
} | |
return valueStack.Peek(); | |
} | |
} | |
class ParseException : Exception | |
{ | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Data.Char | |
data Token = Num Int | |
| T_Plus | T_Sub | |
| T_Mul | T_Div | |
deriving (Show) | |
getPrecedence:: Token -> Int | |
getPrecedence T_Plus = 1 | |
getPrecedence T_Sub = 1 | |
getPrecedence T_Mul = 2 | |
getPrecedence T_Div = 2 | |
evalOp :: Token -> Int -> Int -> Int | |
evalOp T_Plus a b = a + b | |
evalOp T_Sub a b = a - b | |
evalOp T_Mul a b = a * b | |
evalOp T_Div a b = a `div` b | |
tokenizer:: String -> [Token] | |
tokenizer expr = reverse (_tokenizer expr [] []) | |
_tokenizer:: String -> String -> [Token] -> [Token] | |
_tokenizer "" [] previous = previous | |
_tokenizer "" buf previous = ((Num $ read $ reverse buf):previous) | |
_tokenizer (ch:expr) buf previous = | |
if (Data.Char.isDigit ch) then | |
_tokenizer expr (ch:buf) previous | |
else | |
case buf of | |
[] -> | |
case ch of | |
'+' -> _tokenizer expr [] (T_Plus:previous) | |
'-' -> _tokenizer expr [] (T_Sub:previous) | |
'*' -> _tokenizer expr [] (T_Mul:previous) | |
'/' -> _tokenizer expr [] (T_Div:previous) | |
_ -> _tokenizer (ch:expr) [] ((Num $ read $ reverse buf):previous) | |
eval :: [Token] -> Int | |
eval ((Num value):tokens) = _eval tokens [value] [] | |
_eval :: [Token] -> [Int] -> [Token] -> Int | |
_eval [] [value] _ = value | |
_eval (op:(Num num):tokens) numStack [] = | |
_eval tokens (num:numStack) [op] | |
_eval (op:(Num num):tokens) numStack (topOp:opStack) = | |
if (getPrecedence op) > (getPrecedence topOp) then | |
_eval tokens (num:numStack) (op:topOp:opStack) | |
else | |
case numStack of | |
(num1:num2:stack) -> | |
_eval (op:(Num num):tokens) ((evalOp topOp num1 num2):stack) opStack | |
_eval [] (num1:num2:numStack) (topOp:opStack) = | |
_eval [] ((evalOp topOp num1 num2):numStack) opStack |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
type token = Num of int | |
| T_Plus | T_Sub | |
| T_Mul | T_Div | |
let showToken tok = | |
match tok with | |
Num(num) -> "num" | |
| T_Plus -> "T_Plus" | |
| T_Sub -> "T_Sub" | |
| T_Mul -> "T_Mul" | |
| T_Div -> "T_Div" | |
let getPrecedence tok = | |
match tok with | |
T_Plus -> 1 | |
| T_Sub -> 1 | |
| T_Mul -> 2 | |
| T_Div -> 2 | |
let isDigit ch = | |
let ascii_code = Char.code ch in | |
let ascii_0 = Char.code '0' in | |
let ascii_9 = Char.code '9' in | |
ascii_code >= ascii_0 && ascii_code <= ascii_9 | |
let rec _tokenizer input buffer readToken = | |
let str_length = String.length input in | |
let buffer_length = String.length buffer in | |
if str_length = 0 then | |
if buffer_length = 0 then | |
readToken | |
else | |
(Num (Pervasives.int_of_string buffer))::readToken | |
else | |
let first_char = String.get input 0 in | |
let tail = String.sub input 1 (str_length - 1) in | |
if isDigit first_char then | |
_tokenizer tail (buffer ^ (String.make 1 first_char)) readToken | |
else | |
if buffer_length = 0 then | |
match first_char with | |
'+' -> _tokenizer tail "" (T_Plus::readToken) | |
| '-' -> _tokenizer tail "" (T_Sub::readToken) | |
| '*' -> _tokenizer tail "" (T_Mul::readToken) | |
| '/' -> _tokenizer tail "" (T_Div::readToken) | |
else | |
_tokenizer input "" ((Num (Pervasives.int_of_string buffer))::readToken) | |
let tokenizer input = List.rev (_tokenizer input "" []) | |
let evalOp op a b = | |
match op with | |
T_Plus -> a + b | |
| T_Sub -> a - b | |
| T_Mul -> a * b | |
| T_Div -> a / b | |
| _ -> 0 | |
let rec _eval tokens numStack opStack = | |
match tokens with | |
[] -> | |
(match numStack with | |
[value] -> value | |
| num1::num2::ns -> | |
let topOp = List.hd opStack in | |
let result = evalOp topOp num1 num2 in | |
_eval [] (result::ns) (List.tl opStack)) | |
| op::(Num num)::tks -> | |
if (List.length opStack) = 0 then | |
_eval tks (num::numStack) [op] | |
else | |
let topOp = List.hd opStack in | |
let opTl = List.tl opStack in | |
if (getPrecedence op) > (getPrecedence topOp) then (* shift *) | |
_eval tks (num::numStack) (op::opStack) | |
else (* reduce *) | |
(match numStack with | |
num1::num2::ft -> | |
_eval tokens ((evalOp topOp num1 num2)::ft) (opTl) | |
) | |
| (Num num)::tks -> | |
_eval tks (num::numStack) opStack | |
let eval tokens = _eval tokens [] [] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
使用 parsec 来实现解析数学表达式,更能体现函数式的抽象能力和优雅所在。