DPaste - Paste #1376 - pastebin, online compiler and collaboration tool dedicated to D Programming Language

expression parser

Code

import std.range: popFront, empty;
immutable int[256] bps = ['+': 10, '-': 10, '*': 20, '/': 20, '^': 30];
immutable bool[256] ra = ['^': true];
string[] parseExpression(ref string s, int bp=1){
	auto r=(string[]).init, op = "", n=0;
	while(s.length&&s[0]==' ') s.popFront();
	while(!s.empty){
		switch(s[0]){
		case '0': .. case '9':
			for(n=0;n<s.length&&'0'<=s[n]&&s[n]<='9';n++){}
			r~=s[0..n]; s=s[n..$];
			break;
		case '(':
			s.popFront();
			r~=s.parseExpression();
			if(!s.length||s[0]!=')') goto default;
			s.popFront();
			break;
		case ')': return r;
		case '-','+':
			if(!r.length){
				op = s[0..1];
				s.popFront();
				r~=[op,"0"]~s.parseExpression(100); // C-style unary operator precedence
				//r~=[op,"0"]~s.parseExpression(bps[op[0]]+1); // as in mathematics
				break;
			}
			goto case;
		case '*','/','^':
			do{
				op = s[0..1];
				if(bp>bps[op[0]]) return r;
				if(s.length==1||!r.length) goto default;
				s.popFront();
				r=op~r~s.parseExpression(bps[op[0]]+!ra[op[0]]);
			}while(s.length&&bps[s[0]]==bps[op[0]]);
			break;
		case ' ': s.popFront(); break;
		default: return ["Eh?"];
		}
	}
	return r;
}

void main(){
	string term1 = "5 * 3 + 8 * 4";
	string term2 = "2 * 2 + 2";
	string term3 = "5 * (3 + 8) / 4 + 100";
	string term4 = "2 * (2 + 2)";
	string term5 = "* 123";
	string term6 = "+1 * -1";
	string term7 = "1 * 2^3^-4 + 9";
	string term8 = "((-(((1+2)*(3^(3+2)-300)))+22))";
	assert(term1.parseExpression() == ["+", "*", "5", "3", "*", "8", "4"]);
	assert(term2.parseExpression() == ["+", "*", "2", "2", "2"]);
	assert(term3.parseExpression() == ["+", "/", "*", "5", "+", "3", "8", "4", "100"]);
	assert(term4.parseExpression() == ["*", "2", "+", "2", "2"]);
	assert(term5.parseExpression() == ["Eh?"]);
	assert(term6.parseExpression() == ["*", "+", "0", "1", "-", "0", "1"]);
	assert(term7.parseExpression() == ["+","*","1","^","2","^","3","-","0","4","9"]);
	assert(term8.parseExpression() == 
	       ["+", "-", "0", "*", "+", "1", "2", "-", "^", "3", "+", "3", "2", "300", "22"]);
}

Paste info

Author: Guest

Views: 167

Private: no

Expires: Never

Uploaded: 17.08.12 14:47

Votes: 0

Compilation

Compiler: DMD 2.062

Pointer size: m64

Code

Paste info

Compilation

Actions

Confirm

Confirm