首页 > 代码库 > 中缀表达式求值 C++ Stack

中缀表达式求值 C++ Stack

给一个包含小数的中缀表达式 求出它的值

首先转换为后缀表达式然后利用stack求出值

 

转换规则:

如果字符为‘(‘  push

else if 字符为 ‘)‘ 

  出栈运算符直到遇到‘(‘

else if 字符为‘+’,’-‘,’*‘,’/‘

  {

    if 栈为空或者上一个运算符的优先级小于当前运算符

      push

    else

      {

        运算符优先级小于等于栈顶运算符的优先级,出栈

        然后!将当前运算符入栈!

      }

  }

代码

  

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<deque>
#include<iomanip>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<fstream>
#include<memory>
#include<list>
#include<string>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN  1100
#define L 31
#define INF 1000000009
#define eps 0.00000001
/*
1.000+2/4=
((1+2)*5+1)/4=
首先把中缀表达式转换为后缀表达式!(注意点运算符求值)
转换后的结果用一个string vector来表示
然后从前到后求值,pop两个数字 计算结果然后插入到stack中
*/
string str;
vector<string> trans;
stack<char> S;
stack<float> cal;
map<char, int> pri;
void Read()
{
    string tmp;
    trans.clear();
    while (!S.empty())
        S.pop();
    while (!cal.empty())
        cal.pop();
    for (int i = 0; i < str.size() - 1; i++)// 特殊考虑(  )   . 
    {
        if (str[i] == ()
        {
            if (!tmp.empty())
            {
                trans.push_back(tmp);
                tmp.clear();
            }
            S.push(str[i]);
        }
        else if (str[i] == ))
        {
            if (!tmp.empty())
            {
                trans.push_back(tmp);
                tmp.clear();
            }
            while (!S.empty() && S.top() != ()
            {
                string ttt = "";
                ttt.push_back(S.top());
                trans.push_back(ttt);
                S.pop();
            }
            if (!S.empty() && S.top() == ()
                S.pop();
        }
        else if (str[i] == + || str[i] == - || str[i] == * || str[i] == /)
        {
            if (!tmp.empty())
            {
                trans.push_back(tmp);
                tmp.clear();
            }
            if (S.empty() || pri[S.top()]<pri[str[i]])
            {
                S.push(str[i]);
                continue;
            }
            else
            {
                while (!S.empty() && pri[S.top()] >= pri[str[i]])
                {
                    string ttt = "";
                    ttt.push_back(S.top());
                    trans.push_back(ttt);
                    S.pop();
                }
                S.push(str[i]);
            }
        }
        else
        {
            tmp.push_back(str[i]);
        }
    }
    if (!tmp.empty())
    {
        trans.push_back(tmp);
        tmp.clear();
    }
    while (!S.empty())
    {
        string ttt = "";
        ttt.push_back(S.top());
        trans.push_back(ttt);
        S.pop();
    }
}
float solve()//计算转化出的后缀表达式的值
{
    while (!cal.empty())
        cal.pop();
    for (int i = 0; i < trans.size(); i++)
    {
        if (trans[i] == "+" || trans[i] == "-" || trans[i] == "*" || trans[i] == "/")
        {
            float a, b;
            a = cal.top();
            cal.pop();
            b = cal.top();
            cal.pop();
            if (trans[i] == "+")
                cal.push(a + b);
            else if (trans[i] == "-")
                cal.push(b - a);
            else if (trans[i] == "*")
                cal.push(a * b);
            else
                cal.push(b / a);
        }
        else
        {
            cal.push(atof(trans[i].c_str()));
        }
    }
    return cal.top();
}
int main()
{
    int n;
    cin >> n;
    pri[+] = pri[-] = 0, pri[*] = pri[/] = 1, pri[(] = pri[)] = -1;
    while (n--)
    {
        cin >> str;
        Read();
        printf("%.2f\n",solve());
    }
    return 0;
}

 


 

中缀表达式求值 C++ Stack