C/C++ 实现整数四则运算

 问题：实现整数的四则运算（+，-，*，/）

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

 

arithmetic.h

#include <stdio.h>#include <malloc.h>#include <string.h>#include <stdlib.h>#include "Stack.h"class Data{public:double num;char op;};class Arithmetic{private:DoubleStack dStack; //保存四则运算时，后缀表达式中的操作数CharStack cStack; //保存中缀表达式转换成后缀表达式过程中的操作符int isp(char op); //栈内优先级int icp(char op); //栈外优先级public:Data post[100]; //保存后缀表达式int curLen; //后缀表达式数组的实际长度void midTopost(char *c); //把中缀表达式转换成后缀表达式double calculate(); //进行四则运算};

 

Stack.h

#include <stdio.h>#include <malloc.h>//栈节点数据结构class DoubleNode{friend class DoubleStack;private:double value;DoubleNode *next;//构造函数DoubleNode(double value, DoubleNode *p):value(value),next(p){}};//栈，用来保存采用后缀表达式进行四则运算时的操作数class DoubleStack{private: DoubleNode *top;public:DoubleStack():top(NULL){}~DoubleStack();void push(double value);double pop();bool isEmpty(){return top == NULL;}double getTop();};//栈节点数据结构class CharNode{friend class CharStack;private:char value;CharNode *next;//构造函数CharNode(char value, CharNode *p):value(value),next(p){}};//栈，用来保存中缀表达式转换成后缀表达式时的运算符class CharStack{private: CharNode *top;public:CharStack():top(NULL){}~CharStack();void push(char value);char pop();bool isEmpty(){return top == NULL;}char getTop();void makeEmpty();};

 

arithmetic.cpp

#include "arithmetic.h"void Arithmetic::midTopost(char *c){int i = 0;int k;int j;char tmp;char a[100];char num[10];//下面开始把字符串中的操作符（+-*/）放入后缀表达式cStack.makeEmpty();cStack.push('#');//字符串最后都加一个#strcat(c, "#");k = 0;while (c[k] != '/0'){if (c[k] == '+' || c[k] == '-' || c[k] == '*' || c[k] == '/' || c[k] == '('){//如果优先级低，一直退栈，否则入栈while (isp(cStack.getTop()) > icp(c[k])){post[i++].op = cStack.pop();} cStack.push(c[k]);}else if (c[k] == ')'){//一直退栈到'('while (isp(cStack.getTop()) >= icp(')')){tmp = cStack.pop();if (tmp != '('){ post[i++].op = tmp;}}}else if (c[k] == '#'){while (isp(cStack.getTop()) > icp('#')){tmp = cStack.pop();post[i++].op = tmp;}}else if (c[k] >= '0' && c[k] <= '9'){//数字，继续往后获取字符，如果是数字，全部拼装到num中，然后转换成double类型j = 0;memset(num, 0, 10);num[j] = c[k];k = k + 1;while (c[k] >= '0' && c[k] <= '9'){num[++j] = c[k];k++;}post[i].num = atof(num); post[i].op = '#';i++;k--;}else{//其他非法字符，不处理}k++;}curLen = i;}//栈内优先级，栈内优先级大于栈外优先级//'('的栈内优先级应该比所有的操作符都小（除了#）//')'的栈内优先级应该最大//+-的优先级一致，*/的优先级一致int Arithmetic::isp(char op){int pri;switch (op){case '#' : pri = 0;break;case '(' : pri = 1;break;case '+' : pri = 3;break;case '-' : pri = 3;break;case '*' : pri = 5;break;case '/' : pri = 5;break;case ')' : pri = 10;break;}return pri;}//栈外优先级int Arithmetic::icp(char op){int pri;switch (op){case '#' : pri = 0;break;case '(' : pri = 10;break;case '+' : pri = 2;break;case '-' : pri = 2;break;case '*' : pri = 4;break;case '/' : pri = 4;break;case ')' : pri = 1;break;}return pri;}//根据后缀表达式进行四则运算double Arithmetic::calculate(){int i;double result = 0;double left, right;for (i = 0; i < curLen; i++){//如果是数字就入栈if (post[i].op == '#'){dStack.push(post[i].num);}else //如果是操作符，就取出两个数字进行运算{right = dStack.pop(); left = dStack.pop();switch (post[i].op){case '+' : dStack.push(left + right);break;case '-' : dStack.push(left - right);break;case '*' : dStack.push(left * right);break;case '/' : dStack.push(left / right);break;}}}return dStack.pop();}

 

Stack.cpp

#include "Stack.h"DoubleStack::~DoubleStack(){DoubleNode *p;while (NULL != top){ p = top;top = top->next;delete p;}}void DoubleStack::push(double value){top = new DoubleNode(value,top);}double DoubleStack::pop(){if (!isEmpty()){DoubleNode *p;p = top;top = top->next;double nodeValue = p->value;delete p;return nodeValue;}}double DoubleStack::getTop(){return top->value;}CharStack::~CharStack(){CharNode *p;while (NULL != top){ p = top;top = top->next;delete p;}}void CharStack::push(char value){top = new CharNode(value,top);}char CharStack::pop(){if (!isEmpty()){CharNode *p;p = top;top = top->next;char nodeValue = p->value;delete p;return nodeValue;}}void CharStack::makeEmpty(){CharNode *p;while (NULL != top){ p = top;top = top->next;delete p;}}char CharStack::getTop(){return top->value;}

 

main.cpp

#include "arithmetic.h"int main(){char tmp[100];printf("please input a arithmetic express:/n");scanf("%s", tmp);Arithmetic ari = Arithmetic();ari.midTopost(tmp);printf("the result = [%f]/n", ari.calculate());getchar();}