利用栈求解四则运算：求解思路为先将中缀表达式转换为后缀表达式，再利用后缀表达式求解
中缀表达式：运算符出现在两个数字的中间
后缀表达式：运算符出现在两个数字的后面
中缀表达式转后缀表达式规则：
如将 9+(3-1)*3+10/2 转换为 9 3 1 - 3 * + 10 2 / +
规则：
1.从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀 表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级不高于栈顶符号（乘除优先级高于加减），则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
2.如果当前符号或者栈顶符号为左括号，则直接进栈。
3.如果当前符号为右括号，则栈顶依次出栈并输出找到左括号为止。
利用后缀表达式求解思路：
规则：
从左到右遍历后缀表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，直到获得最终结果。
程序如下：
stack.h
#pragma once
#define MAXSIZE 20
// 函数结果状态代码
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
//数据类型
typedef int SElemType;
typedef struct
{
SElemType* base; //栈底指针
SElemType* top; //栈顶指针
int stacksize; //栈可用最大容量
}SqStack;
//顺序栈初始化（构造一个空栈）
Status InitStack(SqStack& S);
//判断顺序栈是否为空
bool StackEmpty(SqStack S);
//求顺序栈长度
int StackLength(SqStack S);
//获取栈顶元素
void GetTop(SqStack S, SElemType& e);
//顺序栈入栈
Status Push(SqStack& S, SElemType e);
//顺序栈出栈
Status Pop(SqStack& S, SElemType& e);
//遍历顺序栈
void StackTraverse(SqStack S);
stack.cpp
#include "stack.h"
#include <iostream>
using namespace std;
//顺序栈初始化（构造一个空栈）
Status InitStack(SqStack& S)
{
S.base = new SElemType[MAXSIZE];
if (!S.base)
{
exit(OVERFLOW); //存储分配失败
}
S.top = S.base; //栈顶指针等于栈底指针
S.stacksize = MAXSIZE;
return OK;
}
//判断顺序栈是否为空
bool StackEmpty(SqStack S)
{
if (!S.base)
{
cout << "栈不存在" << endl;
exit(OVERFLOW);
}
if (S.top == S.base)
return true;
else
return false;
}
//求顺序栈长度
int StackLength(SqStack S)
{
if (!S.base)
{
cout << "栈不存在" << endl;
return 0;
}
return S.top - S.base;
}
//获取栈顶元素
void GetTop(SqStack S, SElemType& e)
{
if (StackEmpty(S))
{
cout << "栈为空" << endl;
return;
}
SElemType* p = S.top;
p--;
e = *p;
}
//顺序栈入栈
Status Push(SqStack& S, SElemType e)
{
if (S.stacksize == StackLength(S))
{
cout << "栈满" << endl;
return ERROR;
}
else if (!S.top)
{
cout << "栈不存在" << endl;
return ERROR;
}
else
{
*S.top = e;
S.top++;
return OK;
}
}
//顺序栈出栈
Status Pop(SqStack& S, SElemType& e)
{
if (StackEmpty(S) | !S.top)
{
cout << "栈为空或者不存在" << endl;
return ERROR;
}
S.top--;
e = *(S.top);
return OK;
}
//遍历顺序栈
void StackTraverse(SqStack S)
{
SElemType* p = S.base; //p指向栈底
while (p != S.top)
{
cout << *p++ << " ";
}
cout << endl;
}
calculation.h
#pragma once
#include <iostream>
using namespace std;
#include "stack.h"
//判断运算符优先级
int GetPriority(char c);
//基本运算处理
int Compute(int x, int y, char op);
//中缀表达式转换为后缀表达式
int* TransformRPN(char* commonExpression);
//利用后缀表达式计算
int ComputeByRPN(int* tranformExpression);
calculation.cpp
#include "calculation.h"
//判断运算符优先级
int GetPriority(char c)
{
switch (c)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
//基本运算处理
int Compute(int x, int y, char op)
{
switch (op)
{
case '+':return x + y;
case '-':return x - y;
case '*':return x * y;
case '/':return x / y;
default:
cout << "请输入正确的操作符" << endl;
return 0;
}
}
//中缀转后缀，如将 9+(3-1)*3+10/2 转换为 9 3 1 - 3 * + 10 2 / +
int* TransformRPN(char commonExpression[])
{
SqStack S;
InitStack(S);
int len = strlen(commonExpression);
int* resExpression = new int[len];
int j = 0; //后缀表达式索引
char data[10];
char c = '0'; //中缀表达式的每一个字符
for (int i = 0; i < len; i++)
{
int k = 0; //操作数解析
while (1) //解析操作数(操作数可能为多位的)
{
c = commonExpression[i];
if (c >= '0' && c <= '9')
{
data[k++] = c;
i++;
}
else
{
break;
}
}
if (k) //如果解析到了操作数，存储解析的操作数
{
data[k] = '\0';
resExpression[j++] = atoi(data);
}
if (StackEmpty(S) || c == '(') //如果栈为空或者为左括号，则直接入栈
{
Push(S, c);
}
else
{
int top; //获取栈顶元素
GetTop(S, top);
if (top == '(') //栈顶元素为左括号就直接进栈
{
Push(S, c);
}
else if (c == ')') //当前字符为右括号，则出栈直到匹配到左括号
{
do
{
Pop(S, top); //弹出栈顶元素
if (top != '(') //左括号不需要记录
{
resExpression[j++] = top; //记录栈顶符号
}
} while (top != '('); //匹配到左括号
}
else if (GetPriority(c) <= GetPriority((char)top)) //如果当前元素字符小于等于栈顶元素
{
while (1) //将小于等于当前元素优先级的元素全部出栈
{
Pop(S, top);
resExpression[j++] = top; //记录栈顶符号
if (!StackEmpty(S)) //如果栈中还有操作符，获取栈顶元素
{
GetTop(S, top);
}
else
{
break;
}
if (GetPriority(c) > GetPriority((char)top) || top == '(')
{
break;
}
}
Push(S, c); //当前元素进栈
}
else //如果当前字符优先级高于栈顶元素，直接进栈
{
Push(S, c);
}
}
}
while (!StackEmpty(S)) //最后将栈中剩下的符号全部输出
{
int top;
Pop(S, top);
resExpression[j++] = top;
}
resExpression[j] = '\0';
return resExpression;
}
//利用后缀表达式计算
int ComputeByRPN(int* tranformExpression)
{
SqStack S;
InitStack(S);
int result = 0;
int i = 0;
while (1) //遍历后缀表达式
{
int c = tranformExpression[i];
if (!c)
{
break;
}
if (GetPriority((char)c)) //如果为操作符
{
int x = 0, y = 0;
Pop(S, x);
Pop(S, y);
result = Compute(y, x, (char)c);
Push(S, result);
}
else //如果为操作数
{
Push(S, c);
}
i++;
}
Pop(S, result);
return result;
}
main.cpp
#include <iostream>
#include "calculation.h"
using namespace std;
int main(int argc, char** argv)
{
char commonExpression[] = "9+(3-1)*3+10/2"; //原始的中缀表达式
//char commonExpression[] = "20*2+(14-5)-24/2";
int* tranformExpression = new int[strlen(commonExpression)];
tranformExpression = TransformRPN(commonExpression); //转换为后缀表达式
//输出中缀表达式
int i = 0;
while (1)
{
int c = tranformExpression[i];
if (!c)
{
break;
}
if (GetPriority((char)c)) //如果为字符
{
cout << (char)c << " ";
}
else
{
cout << c << " ";
}
i++;
}
cout << endl;
int result = ComputeByRPN(tranformExpression);
cout << "计算结果：" << result << endl;
return 0;
}
网友评论