表达式求值和转换

#include<iostream>
using namespace std;
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
#include<unordered_map>

const int maxn = 100020;

stack<double>num;          //数字栈
stack<char>op;          //运算符栈

void eval()                   //用于中缀表达式计算
{
    auto b = num.top();             //考虑运算顺序，先取出来的是第二个运算数
    num.pop();
    auto a = num.top();
    num.pop();

    auto c = op.top();
    op.pop();
    double x = 0;
    if (c == '+')x = a + b;
    else if (c == '-')x = a - b;
    else if (c == '*')x = a * b;
    else x = a / b;
    num.push(x);
}    

bool eval_(char c)                  //用于后缀表达式
{
    auto b = num.top();             //考虑运算顺序，先取出来的是第二个运算数
    num.pop();
    auto a = num.top();
    num.pop();

    int x = 0;
    if (c == '+')x = a + b;
    else if (c == '-')x = a - b;
    else if (c == '*')x = a * b;
    else {
        if (b == 0)
        {
            cout << "Error: " << a << "/0";
            return false;
        }
        x = a / b;

    }
    num.push(x);
    return true;
}

//中缀表达式求值函数

void  evalmerge(string str)
{
    
   
    unordered_map<char, int>pr{ {'+',1},{'-',1},{'*',2},{'/',2} };     //定义一个哈希表，存储优先级

    for (int i = 0; i < str.size(); i++)
    {
        auto c = str[i];
        if (isdigit(c)||c=='-'&&(i==0||str[i-1]=='('))
        {
            int flag = 1, xiaoshuwei = 1;
            double x = c - '0', j = i + 1;
            if (c == '-')
            {
                x = 0;
            }
            while (j < str.size() && (isdigit(str[j])||str[j]=='.'))
            {
                if (str[j] == '.')
                {
                    flag = 0;            //说明是小数了
                    j++;
                    continue;
                }
                if (!flag)                //小数部分
                {
                  
                    x =x+ (1.0*(str[j] - '0'))/pow(10, xiaoshuwei);
                    xiaoshuwei++;
                    j++;
                }
                else
                {
                    x = x * 10 + str[j++] - '0';            //这里的j是要自增的
                }
                
            }
            i = j - 1;                 //别忘记了更新i
            if (c == '-')
            {
                x = -x;
            }
            num.push(x);
        }//取出数字
        else if (c == '+' && (i == 0 || str[i - 1] == '('))
        {
            continue;
        }
        else if (c == '(')  //如果是左括号，入栈即可
        {
            op.push(c);
        }
        else if (c == ')')   //如果是右括号，就意味着我们应该把目前栈里面的运算符都计算完
            //并且我们知道，遇到优先级比当前栈顶优先级低的运算符，我们就会先把栈顶运算符操作完
            //那么，还留在栈里面的操作符都是优先级递增的，所以要从右往左算
        {
            while (op.top() != '(') eval();        //一直计算完整个括号
            op.pop();                         //弹出左括号
        }
        else             //一般情况 
        {
            while (op.size() && pr[op.top()] >= pr[c])//符号栈没空，并且栈顶的运算符优先级大于当前运算符
            {
                eval(); //操作栈顶的运算符
                
               
            }
            op.push(c); //新的运算符压入栈

        }
    }

    while (op.size())   //把最后剩下的运算符操作完
    {
        eval();
    }
    cout << num.top();
}

//后缀表达式求值函数，以#结尾，每个字符用空格隔开 负数粘在一起
void evallast(string str)
{


    for (int i = 0; i < str.size() - 1; i++)
    {
        auto c = str[i];

        if (isdigit(c) || (c == '-' && i + 1 < str.size() - 1 && str[i + 1] != ' '))
        {
            int x = c - '0', j = i + 1;
            if (c == '-')
            {
                x = 0;
            }
            while (j < str.size() - 1 && isdigit(str[j]))
            {
                x = x * 10 + str[j++] - '0';            //这里的j是要自增的
            }
            i = j - 1;                 //别忘记了更新i
            if (c == '-')
            {
                x = -x;
            }
            num.push(x);
        }//取出数字
      
        else if (c != ' ')
        {
            if (num.size() < 2)
            {
                cout << "Expression Error: " << num.top();
                return;

            }
            else
            {
                bool flag = eval_(c);
                if (!flag)
                {
                    return;
                }
            }
        }
    }
    if (num.size() == 1)
        cout << num.top();
    else
    {
        if (num.size() > 1)
        {
            cout << "Expression Error: " << num.top();
        }
    }
   


}

//中缀转后缀
string transe(string str)           
{
    string ans;                           //存储结果表达式

    stack<int>shu;
    stack<char>fu;

    unordered_map<char, int>pr{ {'+',1},{'-',1},{'*',2},{'/',2} };     //定义一个哈希表，存储优先级

    for (int i = 0; i < str.size(); i++)
    {
        auto c = str[i];
        if (isdigit(c) || c == '-' && (i == 0 || str[i - 1] == '('))
        {
            string temp;
            temp += c;
            int x = c - '0', j = i + 1;
           
            while (j < str.size() && (isdigit(str[j]) || str[j] == '.'))
            {
                temp += str[j];
                j++;
                
            }
            i = j - 1;                 //别忘记了更新i
            
            ans += temp;                //直接放到结果表达式中
            ans += " ";
        }//取出数字
        else if (c == '+' && (i == 0 || str[i - 1] == '('))
        {
            continue;

        }
        else if (c == '(')  //如果是左括号，入栈即可
        {
            fu.push(c);
        }
        else if (c == ')')   //如果是右括号，就意味着我们应该把目前栈里面的运算符都计算完
            //并且我们知道，遇到优先级比当前栈顶优先级低的运算符，我们就会先把栈顶运算符操作完
            //那么，还留在栈里面的操作符都是优先级递增的，所以要从右往左算
        {
            while (fu.top() != '(')
            {
                auto tempfu = fu.top();
                fu.pop();
                ans += tempfu;
                ans += " ";

            }
            fu.pop();                         //弹出左括号
        }
        else             //一般情况 
        {
            while (fu.size() && pr[fu.top()] >= pr[c])//符号栈没空，并且栈顶的运算符优先级大于当前运算符
            {
                auto temp = fu.top();
                fu.pop();
                ans += temp;
                ans += " ";


            }
            fu.push(c); //新的运算符压入栈

        }
    }
    while (fu.size())   //把最后剩下的运算符操作完
    {
        auto temp = fu.top();
        fu.pop();
        ans += temp;
        ans += " ";
    }
    ans += '#';
    return ans;


}


int main()
{
    string s;
    cin >> s;
    evalmerge(s);
    cout << endl;

    while (!num.empty())
    {
        num.pop();
    }
    while (!op.empty())
    {
        op.pop();
    }

    string ss = transe(s);
    cout << ss << endl;
  
  


    return 0;
}

热门相关：宴先生缠得要命   高人竟在我身边   都市御魔人   我真没想重生啊   我家影后超甜的