中缀表达式转后缀表达式并计算结果
1. 话不多说,先上镇楼图
2.要实现中缀到后缀的转换
1.如果是数字,直接存入缓冲数组
2.如果是运算符直接入栈(注意优先级)
3.当前入栈字符优先级高于栈顶字符优先级(或者当前栈为空)则直接入栈
4.当前入栈字符优先级低于栈顶字符优先级,则需要出栈栈顶元素(出栈的字符存入缓冲数组),直到当前入栈字符优先级高于栈顶字符优先级
5.左括号"(" ,在栈外默认优先级最高,入栈后默认优先级最低
6.遇到右括号")",则依次弹出栈顶元素直至弹出左括号")"
3.实现前的一些准备
1.创建一个全局缓冲字符数组用来存储转换过程中的字符以及数字
char buffer[SIZE] = { 0 }; //存储缓冲
2.创建一个让字符存入缓冲的函数Put
//字符存入
void Put(char ch)
{
static int index = 0; //静态变量
buffer[index++] = ch;
}
3.设置运算符的优先级
//设置优先级
int Priority(char ch)
{
int ret = 0;
switch (ch)
{
case '+':
case '-':
ret = 1;
break;
case '*':
case '/':
ret = 2;
break;
default:
break;
}
return ret;
}
4.判断是否是左括号,右括号
//是左括号
int isLeft(char ch)
{
return ch == '(';
}
//是右括号
int isRight(char ch)
{
return ch == ')';
}
5.判断是否是运算符
//是否是运算符
int isOperator(char ch)
{
return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}
6.判断是否是数字
//是否是数字
int isNumber(char ch)
{
return (ch >= '0' && ch <= '9');
}
7.实现中缀向后缀的转换
//中缀转后缀 正确返回Correct 错误返回Error
int transForm(const char* str)
{
//创建一个数组栈
char stack[SIZE];
//初始化栈中数据
memset(stack, 0, sizeof(char)*SIZE);
int top = -1;
//遍历字符
while (*str)
{
//判断是否为数字,是数字直接存入buffer
if (isNumber(*str))
{
Put(*str); //存入buffer
}
else if (isOperator(*str)) //判断是否为运算符
{
//比较栈顶字符与入栈字符的优先级 需要弹出所有的栈顶元素大于入栈字符的元素
//top!=-1 表示栈不为空
while (top != -1 && Priority((char)stack[top]) >= Priority(*str))
{
//1.入栈字符优先级低于栈顶元素,出栈栈顶元素存入buffer
Put((char)stack[top--]);
}
//2.入栈字符优先级高于栈顶元素直接入栈或者 空栈直接入栈
stack[++top] = *str; //入栈
}
else if (isLeft(*str)) //左括号 直接入栈
{
stack[++top] = *str; //入栈
}
else if (isRight(*str)) //右括号
{
//栈空返回Error
if (top == -1)
{
printf("栈中数据读取错误!\n");
return Error;
}
//栈顶元素不是左括号
while (!isLeft((char)stack[top]))
{
//不是左括号出栈栈顶元素 并保存至缓冲数组中
Put((char)stack[top--]);
//没有找到
//没有对应的左括号与右括号匹配
if (top == -1)
{
printf("未找到左括号!\n");
return Error;
}
}
//找到左括号将左括号弹出
stack[top--];
}
else
{
printf("有不能识别的字符!\n");
return Error;
}
str++;
}
//遍历结束,弹出栈中的剩下的所有元素
if (*str == '\0')
{
while (top !=-1)
{
//如果还有左括号未跟右括号匹配则返回Error
if (isLeft((char)stack[top]))
{
printf("还存在没有匹配的\"(\"没有\")\"匹配\n");
return Error;
}
//出栈栈中元素并存入缓冲
Put((char)stack[top--]);
}
}
else
{
printf("遍历没有完成!\n");
return Error;
}
return Correct;
}
8.如何实现后缀表达式的计算??
- 遍历后缀表达式
- 如果是数字就入栈
- 如果是运算符就出栈栈中的两个数字(左操作数与右操作数)做运算
- 计算结果入栈继续上述操作,直至栈空
9.实现后缀表达式的计算
//传入字符并返回运算结果
int express(int left, int right, char op)
{
switch (op)
{
case '+':
return left + right;
case '-':
return left - right;
case '*':
return left * right;
case '/':
return left / right;
default:
break;
}
return -1;
}
//后缀表达式的计算
int calculatePosture(const char* str)
{
//创建一个空栈
int stack[SIZE] = { 0 };
int top = -1;
//保存计算后的结果
int ret = 0;
//遍历字符串
while (*str)
{
//如果是数字字符直接入栈
if (isNumber(*str))
{
//将字符转换为数字后再入栈
stack[++top] = *str - '0';
}
//如果是运算符
else if (isOperator(*str))
{
//栈不为空
if (top == -1)
{
printf("栈中数据错误!\n");
break;
}
//出栈栈中数字
int left = stack[top--];
int right = stack[top--];
//做运算
ret = express(left, right, *str);
//运算结果入栈
stack[++top] = ret;
}
else
{
printf("后缀表达式有误!\n");
break;
}
//指针偏移
str++;
//遍历结束并且栈中仅有一个元素
//返回栈中计算结果
if (!(*str) && top == 0)
return ret;
}
}
10.整体代码
#include<stdio.h>
#include<stdlib.h>
#define SIZE 1024
#define Error 0
#define Correct 1
char buffer[SIZE] = { 0 }; //存储缓冲
//字符存入
void Put(char ch)
{
static int index = 0; //静态变量
buffer[index++] = ch;
}
//设置优先级
int Priority(char ch)
{
int ret = 0;
switch (ch)
{
case '+':
case '-':
ret = 1;
break;
case '*':
case '/':
ret = 2;
break;
default:
break;
}
return ret;
}
//是左括号
int isLeft(char ch)
{
return ch == '(';
}
//是右括号
int isRight(char ch)
{
return ch == ')';
}
//是否是运算符
int isOperator(char ch)
{
return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}
//是否是数字
int isNumber(char ch)
{
return (ch >= '0' && ch <= '9');
}
//中缀转后缀 正确返回Correct 错误返回Error
int transForm(const char* str)
{
//创建一个栈
char stack[SIZE];
memset(stack, 0, sizeof(char)*SIZE);
int top = -1;
//遍历字符
while (*str)
{
//判断是否为数字,是数字直接存入buffer
if (isNumber(*str))
{
Put(*str); //存入buffer
}
else if (isOperator(*str)) //判断是否为运算符
{
//比较栈顶元素与新字符的优先级 需要弹出所有的栈顶元素大于新字符的元素
while (top != -1 && Priority((char)stack[top]) >= Priority(*str))
{
//1.新字符优先级低于栈顶元素,出栈栈顶元素存入buffer
Put((char)stack[top--]);
}
//2.新字符优先级高于栈顶元素直接入栈或者 空栈
stack[++top] = *str; //入栈
}
else if (isLeft(*str)) //左括号 入栈
{
stack[++top] = *str; //入栈
}
else if (isRight(*str)) //右括号
{
//判断栈顶是否为左括号,不是就弹出,直到找到左括号
if (top == -1)
{
printf("栈中数据读取错误!\n");
return Error;
}
while (!isLeft((char)stack[top]))
{
//不是左括号出栈 并保存
Put((char)stack[top--]);
//没有找到
if (top == -1)
{
printf("未找到左括号!\n");
return Error;
}
}
//找到左括号弹出
stack[top--];
}
else
{
printf("有不能识别的字符!\n");
return Error;
}
str++;
}
//遍历结束,弹出栈中的所有元素
if (*str == '\0')
{
while (top !=-1)
{
if (isLeft((char)stack[top]))
{
printf("还存在没有匹配的\"(\"没有\")\"匹配\n");
return Error;
}
Put((char)stack[top--]);
}
}
else
{
printf("遍历没有完成!\n");
return Error;
}
return Correct;
}
//后缀表达式的计算
int express(int left, int right, char op)
{
switch (op)
{
case '+':
return left + right;
case '-':
return left - right;
case '*':
return left * right;
case '/':
return left / right;
default:
break;
}
return -1;
}
int calculatePosture(const char* str)
{
//创建一个空栈
int stack[SIZE] = { 0 };
int top = -1;
//保存计算后的结果
int ret = 0;
//遍历字符串
while (*str)
{
//如果是数字直接入栈
if (isNumber(*str))
{
//入栈是将字符转换为数字
stack[++top] = *str - '0';
}
//如果是运算符
else if (isOperator(*str))
{
if (top == -1)
{
printf("栈中数据错误!\n");
break;
}
//出栈数字
int left = stack[top--];
int right = stack[top--];
//做运算
ret = express(left, right, *str);
//运算结果入栈
stack[++top] = ret;
}
else
{
printf("后缀表达式有误!\n");
break;
}
//指针偏移
str++;
//遍历结束并且栈中仅有一个元素
//返回栈中计算结果
if (!(*str) && top == 0)
return ret;
}
}
int main()
{
system("color F0");
char str[SIZE] = { 0 };
printf("请您输入您想转换的中缀表达式!\n");
scanf("%s", str);
if (transForm(str) == Error)
{
printf("出现错误,转换失败!\n");
}
else
printf("转换后的后缀表达式为: %s\n", buffer);
//后缀表达式的计算
int answer = calculatePosture(buffer);
printf("运算结果为: %d\n", answer);
system("pause");
return 0;
}
11.运行示例
