c++实现中缀表达式 转换为后缀表达式

使用栈来计算后缀表达式的值：

9+(3 - 1)*3+10/2;

后缀表达式：所有的符号都是在运算数字的后面出现： 9 3 1 – 3 * + 10  2 / +

规则:

中缀表达式转后缀表达式:

1.从左到右遍历中缀表达式的每个数字和符号，若是数字就打印同时入栈数字栈snum；

2.若是左括号，则将其压入运算符栈sope中；

3.若是右括号，则将sope栈顶的运算符弹出并打印，直到遇到左括号（左括号也出栈，但不输出打印）；

4.若是运算符，若该运算符的优先级大于栈顶运算符的优先级时，则把它压栈；若小于或等于栈顶运算符优先级时，则将栈顶运算符弹出并打印, 同时出栈snum数字按照此运算符运算后结果入栈，再比较新的栈顶运算符，按同样方法处理，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；

5.若中缀表达式中的各对象处理完毕，则把sope栈中存留的运算符依次弹栈输出打印, 同时取snum中的值按照此运算符运算后的结果入栈,直至sope栈空 。snum栈底元素出栈即为计算结果。

 计算规则:

• 创建一个双精度数字栈 snum 来存储操作数。Copy
• 使用 stringstream 将输入字符串 postfix 便于逐个提取 token。
• 使用 while (ss >> token) 循环来逐个读取 token，直到字符串流结束。每次读取都会跳过空格。
• 如果 token 的第一个字符是数字（使用 isdigit 函数判断），则将这个 token 转换为 double 类型并推入栈中。
• 如果 token 不是数字，说明它是一个操作符。
• 从栈中弹出两个元素（x 和 y），注意：弹出顺序是后进先出（LIFO），所以首先弹出的将是最近进入栈的数字
• 根据操作符执行相应的数学运算，并将计算结果压入栈中。
• 针对除法，还需检查除数 y 是否为零，如果是，则抛出异常以避免除以零错误。
• 最后，函数返回栈顶元素，这个值是后缀表达式的计算结果.

完整代码: 

 

#include <iostream>
#include <string>
#include <exception>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
bool isvalidexpression(const string & expression)
{
    for (char ch : expression)
    {
        if (!isdigit(ch) && ch != '+' && ch != '-' && ch != '*' && ch != '/' && ch != ' ')
        {
            return false;
        }
    }
    return true;
}

int precedence(char ch)
{
    switch (ch)
    {
    case '+':
    case'-':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
        return 0;

    }
}

string infixtopostfix(const string& expression)
{
    stack<char> sope;//字符栈
    string postfix = "";//后缀表达式
    string numbuff = "";
    for (size_t i = 0; i < expression.length(); i++)
    {
        char ch = expression[i];
        if (isdigit(ch))
        {
            numbuff += ch;
        }
        else
        {
            if (!numbuff.empty())
            {
                postfix += numbuff;
                postfix += ' ';
                numbuff.clear();
            }

            if (ch == '(')
            {
                sope.push(ch);
            }
            else if (ch == ')')
            {
                while (!sope.empty() && sope.top() != '(')
                {
                    postfix += sope.top();
                    postfix += ' ';
                    sope.pop();
                }
                sope.pop();//出栈'('
            }
            else
            {
                while (!sope.empty() && precedence(sope.top()) >= precedence(ch))
                {
                    postfix += sope.top();
                    postfix += ' ';
                    sope.pop();
                }
                sope.push(ch);
            }
        }
    }
    if (!numbuff.empty())
    {
        postfix += numbuff;
        postfix += ' ';
    }
    while (!sope.empty())
    {
        postfix += sope.top();
        postfix += ' ';
        sope.pop();
    }

    if (!postfix.empty() && postfix.back() == ' ')
    {
        postfix.pop_back();
    }
    return postfix;

}

double evaluatepostfix(const string& postfix)
{
    stack<double>snum;//数字栈
    stringstream ss(postfix);
    string token;
    while (ss >> token)
    {
        if (isdigit(token[0]))
        {
     snum.push(stod(token));//stod 是一个函数，用于将字符串转换为 double 类型的浮点数。
        }
        else
        {
            double x = snum.top(); snum.pop();
            double y = snum.top(); snum.pop();
            switch (token[0])
            {
            case '+':snum.push(x + y); break;
            case'-':snum.push(x - y); break;
            case '*':snum.push(x * y); break;
            case '/':if (y != 0)
            {
                snum.push(x / y);
            }
                    else
            {
                throw runtime_error("Error:Division By Zero");
            }
                    break;
                
            }
        }
    }

    return snum.top();

}

int main()
{
    //输入一个表达式
    string expression;
    cout << "请输入一个算数表达式:(例如2*3*(4+5))" << endl;
    getline(cin , expression);

    //检测有效性
    if (!isvalidexpression(expression))
    {
        cout << "表达式不合法" << endl;
    }
    //将中缀表达式转换为后缀表达式
    string postfix = infixtopostfix(expression);
    cout << "后缀表达式是:"<<postfix << endl;

    //计算后缀表达式的值
    
    try
    {
        double result = evaluatepostfix(postfix);
        cout << "后缀表达式的结果为:" << result << endl;
     }
    catch (runtime_error& e)
    {
        cout << e.what() << endl;
    }

    system("pause");
    return 0;
}