表达式求值(双目运算+-*/())

如果要计算一个中缀表达式,我们首先要将中缀表达式转化为后缀表达式

例如 a + b * c       =>  a b c * +

在遇到每个运算符的时候我们可以将栈顶的两个数运算,然后其结果放入栈中

因此我们可以用两个栈存放 ,一个栈存放数字,另一个栈存放运算符号

如果入栈的是数字,则直接将该数字放入数字栈

符号栈栈顶的运算符号的优先级大于将要入栈的符号, 需要将符号栈栈顶的运算符取出,使数字栈栈顶两个数运算的结果放入数字栈

符号栈栈顶的运算符号的优先级小于将要入栈的符号, 需要将该符号放入符号栈

实现代码如下:可以基本实现浮点数+-/*()运算

例如

2//为样例个数

5.1*6+1=      

31.6

-5=

-5

#include <bits/stdc++.h>

using namespace std;
//比较符号的优先级
char OprateRelation[7][7] =// +    -    *    /    (    )   =
                            {{'>','>', '<', '<', '<', '>', '>'}, //'+'
                            {'>', '>', '<', '<', '<', '>', '>'}, //'-'
                            {'>', '>', '>', '>', '<', '>', '>'}, //'*'
                            {'>', '>', '>', '>', '<', '>', '>'}, //'/'
                            {'<', '<', '<', '<', '<', '=', ' '}, //'('
                            {'>', '>', '>', '>', ' ', '>', '>'}, //')'
                            {'<', '<', '<', '<', '<', ' ', '='}};//'='

string Operation = "+-*/()=";
//返回符号的位置
int GetOperation (char x) {
    for(int i = 0; i < 7; i++)
        if(Operation [i] == x) return i;
    return -1;
}
//返回比较的结果
char CompareOperation(char x, char y) {
    return OprateRelation[GetOperation(x)][GetOperation(y)];
}
//两位数之间的运算
double Get_ans(double x, double y, char opt) {
    if(opt == '-') return x - y;
    else if(opt == '+') return x + y;
    else if(opt == '*') return x * y;
    else return x/y;
}
//求值
double Slove(string Pattern) {
    stack <double> Num;//数 栈
    stack <char> Operate;// 符号 栈
    Operate.push('=');
    int i = 0, flag = 1;
    char Next_char;//目前操作字符的位置
    if(Pattern[0] == '+' || Pattern[0] == '-') Num.push(0);//如果第一位为‘+’或者‘-’代表该数字的正负
    if(Pattern[Pattern.size() - 1] != '=') Pattern += '=';//如果末尾没有 ‘=’ ,添加 ‘=’
    while(flag && i < Pattern.size()) { //flag = 0表示运算完成,i表示已经运算到的位置
        Next_char = Pattern[i];
        if(GetOperation(Next_char) < 0) {//如果是个数字,将其变成一个浮点数然后加入到数栈
            string Number = "";
            Number += Next_char;
            while(GetOperation(Pattern[++i]) < 0) {
                Number += Pattern[i];
            }
            Num.push(atof(Number.c_str()));
        }else {
            char opt = CompareOperation(Operate.top(), Next_char);
            if(opt == '<') {//下一位的符号比栈顶的优先级低,则入栈
                Operate.push(Next_char);
                i++;
            }else if(opt == '>') {////下一位的符号比栈顶的优先级高,则栈顶符号出栈,运算数字栈两个数,然后放入数栈
                char Now_Operate = Operate.top();
                Operate.pop();
                double y = Num.top();
                Num.pop();
                double x = Num.top();
                Num.pop();
                double ans = Get_ans(x, y, Now_Operate);
                Num.push(ans);
            }else {
                Operate.pop();
                if(i == (int)Pattern.length()) flag = 0;
                else i++;
            }
        }
    }
    return Num.top();
}
int main()
{
    int T;
    cin >> T;//测试用例的个数
    string s;
    while(T--) {
        cin >> s;
        cout << Slove(s) << endl;;
    }
    return 0;
}
原文地址:https://www.cnblogs.com/cshg/p/6829953.html