C++ 实现算数表达式求解

说明

1. 算数表达式中只有+-*/这些操作
2. 可以计算浮点数、负数
3. 小数点前面的0可以省略
4. 规定表达式以 # 结尾

• 判断是否为操作符
  非数字和小数点都认为为操作符

bool isOperator(char c)  
{
    return c == '+' || c == '-' || c == '*' || c == '/' || c == ')' || c == '(' || c == '#';
}

• 操作符优先级判断

符号	+	-	*	/	(	)	#
+	>	>	<	<	<	>	>
-	>	>	<	<	<	>	>
*	>	>	>	>	<	>	>
\	>	>	>	>	<	>	>
(	<	<	<	<	<	=
)	>	>	>	>		>	>
#	<	<	<	<	<		=

数列的符号表示在栈顶的符号，横列的表示从表达式中读取的符号
当栈顶为(时，合法表达式中不可能读取到 #
当栈顶为)时，合法表达式中不可能读取到 (
当栈顶为#时，合法表达式中不可能读取到 )

int getIndex(char theta)   //获取theta所对应的索引
{
    int index = 0;
    switch (theta)
    {
    case '+':
        index = 0;
        break;
    case '-':
        index = 1;
        break;
    case '*':
        index = 2;
        break;
    case '/':
        index = 3;
        break;
    case '(':
        index = 4;
        break;
    case ')':
        index = 5;
        break;
    case '#':
        index = 6;
    default:break;
    }   
    return index;
}

char getPriority(char theta1, char theta2)   //获取theta1与theta2之间的优先级                                                                                                                                    
{
    const char priority[][7] =     //算符间的优先级关系
    {
        { '>','>','<','<','<','>','>' },
        { '>','>','<','<','<','>','>' },
        { '>','>','>','>','<','>','>' },
        { '>','>','>','>','<','>','>' },
        { '<','<','<','<','<','=','0' },
        { '>','>','>','>','0','>','>' },
        { '<','<','<','<','<','0','=' },
    };

    int index1 = getIndex(theta1);
    int index2 = getIndex(theta2);
    return priority[index1][index2];
}

• 合法性判断
  这里只判断括号是否匹配

bool isValidExpression(const string& expression) 
{                                                                                                                                                               
    stack<char> brackets;
    for (char c : expression) 
    {
        if (c == '(') 
        {
            brackets.push(c);
        } 
        else if (c == ')') 
        {
            if (brackets.empty() || brackets.top() != '(') 
            {
                return false;
            }   
            brackets.pop();
        }   
    }   
    return brackets.empty();
}

• 在单独的+或-前补0
  为了正确处理负数和带符号的正数

std::string addZero(const std::string& input)
{
    std::string result;
    result.reserve(input.size() + input.size() / 2); // 预留足够的空间，避免频繁的重新分配内存

    for (size_t i = 0; i < input.size(); ++i) 
    {
        if ((input[i] == '-' || input[i] == '+') && (i == 0 || input[i - 1] == '(')) {
            result.push_back('0');
        }
        result.push_back(input[i]);
    }
    return result;
}

• 清洗数据
  分离表达式和数字

// 判断一个字符串能否被转为浮点数
bool isNumber(const std::string& str)
{
    try
    {
        std::stod(str);
    }
    catch (std::exception& e)
    {
        return false;
    }
    return true;

}

bool formatInput(const string& str, std::vector<std::string>& result)
{
    std::string input = addZero(str);
    string num;
    for (auto ch : input)
    {
        if (::isdigit(ch) || ch == '.')
        {
            num += ch;
        }
        else
        {
            if (!num.empty())
            {
                if (!isNumber(num))
                {
                    return false;
                }
                result.push_back(num);
                num.clear();
            }
            result.push_back(string(1, ch));
        }
    }
    if (!num.empty())
    {
        if (!isNumber(num))
        {
            return false;
        }
        result.push_back(num);
        num.clear();
    }
    return true;
}

• 计算表达式的值
  在计算表达式的值的时候会继续判断该表达式是否合法

1. 不能连续出现+-*/操作符
2. 不能除以0
3. 操作符前后必须有可以运算的数字

bool evaluate(const std::string& input, double& value)
{
    std::vector<std::string> expression;
    bool valid  = formatInput(input, expression);
    if (!valid) return false;
    std::stack<char> operators;
    std::stack<double> operands;
    operators.push('#');
    for (int i = 0; i < expression.size();)
    {
        auto exp = expression[i];
        if (!isOperator(exp[0]))
        {
            operands.push(std::stod(exp));
            i++;
        }
        else
        {
            char c = exp[0];
            switch (getPriority(operators.top(), c))   //获取运算符栈opter栈顶元素与c之间的优先级，用'>'，'<'，'='表示
            {
            case '<':               //<则将c入栈opter
            {
                operators.push(c);
                i++;
                break;
            }
            case '=':               //=将opter栈顶元素弹出，用于括号的处理
            {
                operators.pop();
                i++;
                break;
            }
            case '>':               //>则计算
            {
                if (operands.empty()) return false;
                char theta = operators.top();
                operators.pop();
                double a = operands.top();
                operands.pop();
                if (operands.empty()) return false;
                double b = operands.top();
                operands.pop();
                if (theta == '/' && a == 0) return false;
                operands.push(calculate(b, theta, a));
                break;
            }
            case '0':
            {
                return false;
            }
            }
        }
    }
    // 数字栈中不存在数字，无法计算，返回法false
    if (operands.empty()) return false;
    value = operands.top();
    return true;
}