Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
parsing math expression
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
{
}
}
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
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 [] []
@Lucifier129

This comment has been minimized.

Copy link

Lucifier129 commented Aug 21, 2018

使用 parsec 来实现解析数学表达式,更能体现函数式的抽象能力和优雅所在。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.