Skip to content

Instantly share code, notes, and snippets.

@inkedawn inkedawn/expr.cpp
Last active Oct 7, 2018

Embed
What would you like to do?
简单的表达式解析与运算求值(支持整数/浮点运算、有优先级的二元运算(加减乘除))
#include <string>
#include <memory>
#include <cassert>
class Expr{
public:
virtual double evaluate() = 0;
virtual std::string toString() = 0;
virtual std::string toRPN() = 0; // 逆波兰表示法
class Op {
public:
Op(const char& op_input)
: op(op_input)
{}
::std::string toString() {
return ::std::string().assign(1, op);
}
operator char() {
return this->op;
}
operator ::std::string() {
return this->toString();
}
protected:
char op;
};
};
class BinaryExpr : public Expr{
public:
class BinaryOp : public Expr::Op {
public:
BinaryOp(const char& op_input)
: Expr::Op(op_input)
{}
virtual double apply(std::shared_ptr<Expr> first, std::shared_ptr<Expr> second) {
switch (op) {
case '+':
return first->evaluate() + second->evaluate();
case '-':
return first->evaluate() - second->evaluate();
case '*':
return first->evaluate() * second->evaluate();
case '/':
return first->evaluate() / second->evaluate();
}
assert(false);
return 0;
}
};
BinaryExpr(const std::shared_ptr<Expr>& first_input,
const std::shared_ptr<Expr>& second_input,
const BinaryExpr::BinaryOp& op_input
)
: first(first_input), second(second_input), op(op_input)
{}
double evaluate() override {
return op.apply(first, second);
}
std::string toString() override {
return first->toString() + " " + op.toString() + " " + second->toString();
}
std::string toRPN() override {
return first->toRPN() + " " +second->toRPN() + " " + op.toString();
}
static std::shared_ptr<BinaryExpr> Create(const std::shared_ptr<Expr>& first,
const std::shared_ptr<Expr>& second,
const BinaryExpr::BinaryOp& op
) {
auto expr = std::make_shared<BinaryExpr>(first, second, op);
return expr;
}
private:
BinaryOp op;
std::shared_ptr<Expr> first;
std::shared_ptr<Expr> second;
};
class IntExpr : public Expr{
public:
double evaluate() override {
return value;
}
std::string toString() override {
return std::to_string(value);
}
std::string toRPN() override {
return std::to_string(value);
}
static std::shared_ptr<IntExpr> Create(const int& value) {
auto expr = std::make_shared<IntExpr>();
expr->value = value;
return expr;
}
private:
int value;
};
class Float64Expr : public Expr{
public:
double evaluate() override {
return value;
}
std::string toString() override {
return std::to_string(value);
}
std::string toRPN() override {
return std::to_string(value);
}
static std::shared_ptr<Float64Expr> Create(const double& value) {
auto expr = std::make_shared<Float64Expr>();
expr->value = value;
return expr;
}
private:
double value;
};
#include <iostream>
#include <string>
#include <memory>
int main() {
using std::string;
using std::cin;
using std::cout;
using std::endl;
string exprStr; cin >> exprStr;
auto expr = parseExpr(exprStr);
cout << expr->toString() << endl
<< expr->toRPN() << endl
<< expr->evaluate()<< endl;
return 0;
}
#include <iostream>
#include <string>
#include <memory>
#include <stack>
#include <forward_list>
#include <cctype>
#include <cassert>
#include <cmath>
int getOpPriority(char op) {
switch (op) {
case '+':
[[fallthrough]]
case '-':
return 1;
case '*':
[[fallthrough]]
case '/':
return 2;
}
assert(false);
return -1;
}
std::shared_ptr<Expr> parseExpr(const std::string& str) {
// now only support binary operator
std::stack< std::shared_ptr<Expr> > exprs;
std::stack< BinaryExpr::BinaryOp > ops;
std::forward_list<char> digitChars;
bool floatFlag = false;
auto createDigitExpr = [&](){
if (floatFlag) {
// TODO: 解析方法可优化
digitChars.reverse();
double digit = std::stod(std::string(digitChars.begin(), digitChars.end()));
digitChars.clear();
exprs.push( Float64Expr::Create(digit) );
floatFlag = false;
//std::clog << "create " << digit << std::endl;
return;
}
int digit = 0;
int i = 0;
while (!digitChars.empty()) {
digit += (digitChars.front() - '0') * pow(10, i);
digitChars.pop_front();
i++;
}
//std::clog << "create " << digit << std::endl;
exprs.push( IntExpr::Create(digit) );
};
auto createBinaryExpr = [&](){
assert(!exprs.empty());
std::shared_ptr<Expr> b = exprs.top(); exprs.pop();
assert(!exprs.empty());
std::shared_ptr<Expr> a = exprs.top(); exprs.pop();
assert(!ops.empty());
BinaryExpr::BinaryOp op = ops.top(); ops.pop();
//std::cout << "create " << a->toString() << " " << op << " "<< b->toString() << std::endl;
std::shared_ptr<BinaryExpr> expr = BinaryExpr::Create(a, b, op);
exprs.push(expr);
};
for (char c : str) {
if (std::isdigit(c)) {
digitChars.push_front(c);
}else if (!digitChars.empty() && c=='.') {
floatFlag = true;
digitChars.push_front(c);
}else{
// create digit expression
if (!digitChars.empty()) {
createDigitExpr();
}
// create binary expression
while (!ops.empty() && getOpPriority(c)<=getOpPriority(ops.top()) ) {
createBinaryExpr();
}
ops.push(BinaryExpr::BinaryOp(c));
}
}
// process the rest
if (!digitChars.empty()) {
createDigitExpr();
}
while (!ops.empty()) {
createBinaryExpr();
}
return exprs.top();
}
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.