C++实现支持浮点（x.x）的四则运算（带括号）

于 2015-08-05 15:44:04 发布
阅读量2.2k 收藏 6
点赞数
分类专栏： 数据结构 文章标签： C++ 逆波兰式 四则运算
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Reformatsky/article/details/47298385
版权

思路：首先利用栈A把四则运算的字符串从中序表达式转换成后序表达式；然后对后序表达式，如果是数字则保存到另一个栈B中，如果是运算符（+,-,*,/）就从栈B中依次获取栈顶两个操作数进行运算，运算结果再压栈B，如此反复，最终栈B中最后的值就是运算结果。

#define MAX_LENGTH  500

class Data
{
public:
    double num;
    char op;
};

class FourArithmeticOP
{
private:
    Stack<double> numStack;   //进行四则运算时，保存后序表达式中的操作数
    Stack<char> opStack;         //保存中序表达式转换成后序表达式过程中的操作符
    int InStackPriority(char op);   //进入栈内后的优先级
    int NormalPriority(char op);    //普通表达式中的优先级
public:
    Data post[MAX_LENGTH];    //保存后序表达式
    int postLength;                     //后序表达式数组的实际长度
    void InorderToPostorder(char *cExp);  //把中序表达式转换成后序表达式
    double Calculate();                //进行四则运算
};

//对四则运算符，栈内优先级提升，'('的栈内优先级应该比所有的操作符都小，')'的栈内优先级应该最大
//+-的优先级一致，*/的优先级一致
int FourArithmeticOP::InStackPriority(char op)
{
    int priority;
    switch (op)
    {
    case '+' : priority = 3;
        break;
    case '-' : priority = 3;
        break;
    case '*' : priority = 5;
        break;
    case '/' : priority = 5;
        break;
    case '(' : priority = 1;
        break;
    case ')' : priority = 10;
        break;
    default:  priority = 0;
        break;
    }
    return priority;
}

int FourArithmeticOP::NormalPriority(char op)
{
    int priority;
    switch (op)
    {
    case '+' : priority = 2;
        break;
    case '-' : priority = 2;
        break;
    case '*' : priority = 4;
        break;
    case '/' : priority = 4;
        break;
    case '(' : priority = 10;
        break;
    case ')' : priority = 1;
        break;
    default: priority = 0;
        break;
    }
    return priority;
}

void FourArithmeticOP::InorderToPostorder(char *cExp)
{
    char num[10];

    //把字符串中的数字和操作符（+-*/）放入后序表达式
    opStack.makeEmpty();

    //加入一个优先级最低的特殊字符，使opStack不为空
    opStack.push('&');
    
    int index = 0;
    postLength = 0;
    while (cExp[index] != '\0')
    {
        if (cExp[index] == '+' || cExp[index] == '-' || cExp[index] == '*' || cExp[index] == '/' || cExp[index] == '(')
        {
            //优先级高于当前操作符的栈内操作符出栈
            while (NormalPriority(cExp[index]) < InStackPriority(opStack.getTop()))
            {
                post[postLength++].op = opStack.pop();
            }
            opStack.push(cExp[index]);
        }
        else if (cExp[index] == ')')
        {
            //一直退栈到'('
            while (opStack.getTop() != '(') 
            {
                post[postLength++].op = opStack.pop();
            }

            // '(' 出栈
            opStack.pop();
        }
        else if (cExp[index] >= '0' && cExp[index] <= '9')
        {
            //数字
            int j = 0;
            memset(num, 0, 10);
            while (cExp[index] >= '0' && cExp[index] <= '9')
            {
                num[j++] = cExp[index++];
            }
            index--;

            post[postLength].num = atof(num);
            post[postLength].op = '&';
            postLength++;
        }
        else
        {
            //非法字符，不处理
        }
        index++;
    }

    while (opStack.getTop() != '&')
     {
         post[postLength++].op = opStack.pop();
     }

     // '&' 出栈
     opStack.pop();
}

//根据后序表达式进行四则运算
double FourArithmeticOP::Calculate()
{
    double left, right;

    numStack.makeEmpty();

    for (int i = 0; i < postLength; i++)
    {
        if (post[i].op == '&')
        {
            // 数字
            numStack.push(post[i].num);
        }
        else
        {
            //操作符，取出两个数字进行运算
            right = numStack.pop();
            left = numStack.pop();
            switch (post[i].op)
            {
            case '+' : numStack.push(left + right);
                break;
            case '-' : numStack.push(left - right);
                break;
            case '*' : numStack.push(left * right);
                break;
            case '/' : numStack.push(left / right);
                break;
            }
        }
    }

    return numStack.pop();
}
以上内容转载自 http://blog.163.com/wmk_2000_ren/blog/static/138846192201031211285589/

以下为本人的代码，其中计算优先级的部分借用了上述的代码。

所有操作都封装到了一个类中

#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <vector>
#include <list>
#include <stack>
#include <queue>

using namespace std;

typedef struct{
    double operand;
    char opt;
}PostNode;

class FourArithmeticOP
{
private:
    const char NO_OPERATOR = 0x00;

    stack< char , list<char> > OpStack;
    queue< PostNode , list<PostNode> > PostStr;
    stack< double , list<double> > OperandStack;


public:
    FourArithmeticOP() {
        OpStack.push('#');
    }

    ~FourArithmeticOP() {

    }

    int IsNumOrDot(char chra);
    int IsOperator(char chra);
    int NormalPriority(char opt);
    int StackPriority(char opt);

    int InorderToPost(char *cExp);
    void ShowPostStr();
    double Calculate();
};


<span style="font-size:18px;">int FourArithmeticOP::IsNumOrDot(char chra)
{
    if( (chra >= '0' && chra <= '9') || chra == '.' )
        return 1;
    return 0;
}

int FourArithmeticOP::IsOperator(char chra)
{
    if(chra == '+' || chra == '-' ||
            chra == '*' || chra =='/' ||
            chra =='(' || chra == ')')
        return 1;
    return 0;
}

int FourArithmeticOP::NormalPriority(char opt)
{
    int priority;
    switch (opt)
    {
    case '+' : priority = 2;
        break;
    case '-' : priority = 2;
        break;
    case '*' : priority = 4;
        break;
    case '/' : priority = 4;
        break;
    case '(' : priority = 10;
        break;
    case ')' : priority = 1;
        break;
    default: priority = 0;
        break;
    }
    return priority;
}
//相同运算符，在栈中优先级更高
int FourArithmeticOP::StackPriority(char opt)
{
    int priority;
    switch (opt)
    {
    case '+' : priority = 3;
        break;
    case '-' : priority = 3;
        break;
    case '*' : priority = 5;
        break;
    case '/' : priority = 5;
        break;
    case '(' : priority = 1;
        break;
    case ')' : priority = 10;
        break;
    default:  priority = 0;
        break;
    }
    return priority;
}

int FourArithmeticOP::InorderToPost(char *cExp)
{
    string NumStr;
    //    double num;
    PostNode node;

    int i = 0;
    while(i < strlen(cExp)) {
        NumStr.clear();
        while(IsNumOrDot(cExp[i])) {
            NumStr += cExp[i];
            i++;
        }//get int or float
        if(!NumStr.empty()) {
            if('.' == NumStr.at(NumStr.length() - 1) ||
                    '.' == NumStr.at(0))
            {
                cout << "valid float : " << NumStr << endl;
                return 0;
            }
            node.operand = atof(NumStr.c_str());
            node.opt = NO_OPERATOR;
            PostStr.push(node);
        }
        else if(IsOperator(cExp[i])) {
            if(')' == cExp[i]) {</span>
<span style="font-size:18px;"><span style="white-space:pre">		</span>//遇到 ) 则 一直弹出直到 (
                while('(' != OpStack.top()) {
                    if('#' == OpStack.top()) {
                        cout << "parenthesis error" << endl;
                        return 0;
                    }
                    //pop out pair parenthesis
                    node.opt = OpStack.top();
                    PostStr.push(node);
                    OpStack.pop();
                }
                OpStack.pop(); //pop out '('
                i++;
                continue;
            }
            while(NormalPriority(cExp[i]) <= StackPriority(OpStack.top()))
            {
                node.opt = OpStack.top();
                PostStr.push(node);
                OpStack.pop();
            }
            OpStack.push(cExp[i]);
            i++;
        }
        else {
            cout << "valid operator : " << cExp[i] << endl;
            return 0;
        }
    }
    while('#' != OpStack.top()) {
        node.opt = OpStack.top();
        PostStr.push(node);
        OpStack.pop();
    }
    return 1;
}

double FourArithmeticOP::Calculate()
{
    PostNode node;
    double operand_1;
    double operand_2;
    char Operator;
    while(!PostStr.empty()) {
        Operator = PostStr.front().opt;
        //operand
        if(NO_OPERATOR == Operator) {
            operand_1 = PostStr.front().operand;
            OperandStack.push(operand_1);
            //            Operator = PostStr.front().opt;
        }
        else {
            //handle operator
            operand_2 = OperandStack.top();
            OperandStack.pop();
            operand_1 = OperandStack.top();
            OperandStack.pop();
            switch(Operator){
            case '+' : OperandStack.push(operand_1 + operand_2);
                break;
            case '-' : OperandStack.push(operand_1 - operand_2);
                break;
            case '*' : OperandStack.push(operand_1 * operand_2);
                break;
            case '/' :
                if(0 == operand_2) {
                    cout << "operand_2 = 0 while /" << endl;
                    return 0;
                }
                else {
                    OperandStack.push(operand_1 / operand_2);
                }
            }
        }
        PostStr.pop();
    }
    double res = OperandStack.top();
    OperandStack.pop();
    return res;
}</span>

评论 1
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值