原帖地址：http://www.cppblog.com/jb8164/archive/2008/01/02/40211.html
// 头文件 Calc.h
#ifndef __CALC_H__
#define __CALC_H__
#include <stack>
#define ascii_int(x) (x >= 0x30 && x <= 0x39) ? (x - 0x30) : (x)
const int GREATER = 1;
const int EQUAL = 0;
const int LESS = -1;
class Calculate 
{
public:
int evaluteExpr(char *exp);
private:
int getLevel(char ch);
bool isOperator(char ch);
int compareOpteratorLevel(char inputChar, char optrStackTop);
int calc(int num1, int num2, char op);
void evaluate(char ch);
private:
std::stack<int> _opnd_stack;
std::stack<char> _optr_stack;
static char _optr[];
static int _level[];
};
#endif
// 头文件的实现代码 Calc.cxx
#include "Calc.h"
char Calculate::_optr[] = {'#', '(', '+', '-', '*', '/', ')'};
int Calculate::_level[] = { 0, 1, 2, 2, 3, 3, 4 };
// Get current operator level for calculating
int Calculate::getLevel(char ch) {
for (int i = 0; *(_optr+i) != '\0'; ++i)
if (*(_optr+i) == ch)
return *(_level+i);
}
// Calculate the operands
int Calculate::calc(int num1, int num2, char op) {
switch (op)
{
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
case '/':
return num1 / num2;
}
}
// judge inputing character is operator or not
bool Calculate::isOperator(char ch) {
for (char *p = _optr; *p != '\0'; ++p)
if (*p == ch)
return true;
return false;
}
// Compare level of input operator and the top operator of operator stack
int Calculate::compareOpteratorLevel(char inputChar, char optrStackTop) {
// if (inputChar == '(' && optrStackTop == ')')
// return EQUAL;
// else
if (inputChar == '(')
return GREATER;
if (inputChar == ')' && optrStackTop == '(')
return EQUAL;
else if (inputChar == ')')
return LESS;
if (inputChar == '#' && optrStackTop == '#')
return EQUAL;
// else if (inputChar == '#')
// return LESS;
return (getLevel(inputChar) > getLevel(optrStackTop)) ? GREATER : LESS;
}
// Evaluate value while inputing operators
void Calculate::evaluate(char ch) {
char op;
int num, result;
if (!isOperator(ch)) {
_opnd_stack.push(ascii_int(ch));
return ;
}
switch (compareOpteratorLevel(ch, _optr_stack.top()))
{
case GREATER :
_optr_stack.push(ch);
break;
case EQUAL :
_optr_stack.pop();
break;
case LESS :
num = _opnd_stack.top();
_opnd_stack.pop();
result = _opnd_stack.top();
_opnd_stack.pop();
op = _optr_stack.top();
_optr_stack.pop();
result = calc(result, num, op);
_opnd_stack.push(result);
evaluate(ch);
break;
}
}
// Evaluate user specified expression
int Calculate::evaluteExpr(char *exp) {
_optr_stack.push('#');
for (char *p =exp; *p != '\0'; ++p )
evaluate(*p);
int result = _opnd_stack.top();
_opnd_stack.pop();
return result;
}
// 测试代码 calc_test.cxx
#include <iostream>
#include "Calc.h"
using namespace std;
int main(void) {
Calculate *calc = new Calculate();
cout << "1+3*(4+7) = "
<< calc->evaluteExpr("1+3*(4+7)#")
<< endl;
cout << "((1+2)) = "
<< calc->evaluteExpr("((1+2))#")
<< endl;
cout << "3*8+9/7-5-9+(1-9)/4 = "
<< calc->evaluteExpr("3*8+9/7-5-9+(1-9)/4#")
<< endl;
cout << "(6-7)*(5+9) = "
<< calc->evaluteExpr("(6-7)*(5+9)#")
<< endl;
cout << "0*8+0/6-9+(7-1) = "
<< calc->evaluteExpr("0*8+0/6-9+(7-1)#")
<< endl;
delete calc;
}
用 MinGW/G++ 3.4.5 编译如下:
g++ -o test.exe Calc.cxx Calc_test.cxx
作为一个演示算法够了， 但代码还是有一些缺点:
(1) 只能处理一位数的加、减、乘、除表达式计算(可带括号)
(2) 没有任何错误处理，例如不能在表达式中有空格