当前位置 博文首页 > ice_elephant的博客：数据结构算法之通过栈实现四则运算
它的基本结构形式是的一个栈顶指针，还有一个栈底指。
typedef int Elemdate;
typedef struct _Stack{
Elemdate *top;
Elemdate *base;
}Stack;
//这就是栈的一个基本构造形式
运算符是这样的: 15+73(2+1) 我们要计算得的数字是这样的,
利用栈的中缀法则我们需要创建两个栈 一个栈存入操作数 另一个栈存入操作符号
它的运算顺序是这样的 15+73(2+1)
首先我们让数字15进栈，但是我们这里输入的是字符串那么我们如何让
//栈的四则运算，支持有括号的形式
//5+7*3*(2+1)
#include<stdio.h>
#include<Windows.h>
#include<iostream>
#include<string>
using namespace std;
typedef int Elemdate;
#define MAX_SIZE 10
typedef struct _Stack {
Elemdate* base;
Elemdate* top;
}Stack;
//栈的初始化
bool initStack(Stack& stack) {
stack.base = new int[MAX_SIZE];
if (!stack.base) {
printf("栈初始化失败!\n");
return false;
}
stack.top = stack.base;
return true;
}
//获取栈顶元素
Elemdate* getTop(Stack& stack) {
if (stack.top != stack.base) {
return stack.top - 1;
}
else {
return NULL;
}
}
//入栈
bool PushStack(Stack& stack, int date) {
if (stack.top - stack.base == MAX_SIZE) {
printf("栈空间已满，入栈失败!\n");
return false;
}
*(stack.top++) = date;
return true;
}
//出栈
bool PopStack(Stack& stack, int& date) {
if (stack.base == stack.top) {
printf("无元素可出栈!\n");
return false;
}
date = *(--stack.top);
return true;
}
//判断栈是否为空
bool isEmpty(Stack& stack) {
if (stack.base == stack.top) {
return true;
}
return false;
}
//判断栈是否已满
bool isFully(Stack& stack) {
if (stack.top - stack.base == MAX_SIZE) {
return true;
}
return false;
}
//销毁栈
void destoyedStack(Stack& stack) {
if (!&stack) return;
delete[MAX_SIZE] stack.base;
stack.base = stack.top = NULL;
}
//获取以元素个数
int getElemdateCount(Stack& stack) {
return (stack.top - stack.base);
}
//四则运算机算
int operatored(int ldate, int opt, int rdate) {
int result = 0;
cout << "left:" << ldate << "right" << rdate << "opt" << (char)opt << endl;
switch (opt) {
case '+':
result = ldate + rdate;
break;
case '-':
result = ldate - rdate;
break;
case '*':
result = ldate * rdate;
break;
case '/':
result = ldate / rdate;
break;
default:
break;
}
//cout << "reslut:" << result << endl;
return result;
}
//判断栈顶元素的优先级和当前获取的运算符优先级
bool isLarger(const int& input, const int& top) {//top代表的是栈顶符号元素，input代表的是当前符号元素
/*if((rhs=='+'|rhs=='-')&&(lhs=='*'||lhs=='/')){
return true;
}else
{
return false;
}*/
//这里
//如果当前元素比栈顶元素大直接入栈，否则要计算在入栈
//8/大于
if ((input == '*' || input == '/') && (top == '-' || top == '+' || top == '('))
return true;
else
return false;
if ((input == '+' || input == '-') && top != '(')
return true;
else
return false;
if ((input == '(')) //直接入栈
return true;
}
int caculate(string input) {
/*
入栈顺序
5先进操作数栈
+直接进操作符栈
7直接进操作数栈
*直接进操作符栈
3直接进操作数栈
遇到*先不进栈
先计算7*3
注意从操作数栈 出栈元素 3 7 3先出放在右边 7后出放在左边 中间是*操作符，那么从程序中怎么判断呢？
然后得到运算吧结果 21 将 21 入操作数字栈 现在操作数栈 5 21 操作符栈 +
*入操作符栈
遇到( 直接入操作符栈 2直接入操作数栈 +直接入操作符栈 然后在是1直接入操作数栈
此时操作数栈为 5 21 2 1
操作符栈为 + * ( +
先执行括号里面的
出栈2 1 和+，1在右侧 2 在左侧 + 计算 2+1 = 3，出栈标识符是，遇到了'('那么这个符号栈就不出元素了 3入栈 (出栈
5 21 3 + *
出栈 21 3 * 21*3=63
5 63 +
出栈 5 63 +
计算 5 + 63 = 68
然后 入栈返回栈顶元素
*/
bool shiftis0 = false;
int tmpDATE;
int tmpOPT;
Stack stack_date; //操作数
Stack stack_opt;
//PushStack(stack_opt,'#');
initStack(stack_date);
initStack(stack_opt);
int ldate = 0;
int result = 0;
//当然里面最多只可能有两个操作符
int TemOpt;
int TmpLdate = 0, TmpRdate = 0;
//15+7*3*(2+1)
for (int i = 0; i < input.length(); i++) {
//if(isspace(input[i])) continue;
if (getTop(stack_date)) tmpDATE = *getTop(stack_date);
if (getTop(stack_opt)) tmpOPT = *getTop(stack_opt);
if (isdigit(input[i])) {
//如果是数字并且为空，直接入栈
// if(isEmpty(stack_date)){
//ldate *=10;
ldate = input[i] - '0';
while (isdigit(input[i + 1])) {
//判断接下来的i+1是数字还是字符，如果是数字直接推进去，否则
i++;
ldate *= 10;
ldate = ldate + input[i] - '0';
}
PushStack(stack_date, ldate);//别急入栈，这里面我想要的是15入栈而不1入栈，怎么办
cout << "操作数" << ldate << "入栈" << endl;
ldate = 0;
continue; // }
}
if (input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/' || input[i] == '(' || input[i] == ')') {
//这些运算符的时候
if (input[i] == '(') {
PushStack(stack_opt, input[i]);
cout << "操作符" << (char)input[i] << "入栈" << endl;
shiftis0 = true;
continue;
}
if (isEmpty(stack_opt) && input[i]) {
cout << "运算符" <<
