首先需要区分中缀表达式与后缀表达式（中缀转为后缀即可进行计算）：
例如中缀表达式为12+3-(6+2)*2-15/3
那么所求的后缀表达式的步骤为
1. 判断12是数字，不入栈，输出12。即为 12
2. 判断+是运算符，入栈。即为 12
3. 判断3是数字，不入栈，输出3。即为 12 3
4. 判断-是运算符，入栈，此时需要判断符号之间的优先级，低于栈顶符号才可以输出。输出+。即为 12 3 +
5. 判断(是特殊符号，需要特殊定义，入栈，但不输出。即为 12 3 +
6.判断 6是数字，不入栈，输出。即为 12 3 +6
7.判断+是运算符，入栈，不输出。即为 12 3 +6
8.判断2是数字，不入栈，输出。即为 12 3 +6 2
9.判断)是特殊符号，入栈，前面有(，即将之前存入的内容全部输出。即为 12 3 +6 2 +
10. 判断*是运算符，入栈，不输出。即为12 3 +6 2 +
11. 判断2是数字，不入栈，输出。即为 12 3 +6 2 +2
12. 判断-是运算符，而*的优先级高于-，所以在-之前的内容全部输出。即为 12 3 +6 2 +2 *-
13.判断15是数字，不入栈，输出。即为 12 3 +6 2 +2 *- 15
14.判断/是运算符，入栈，不输出。即为 12 3 +6 2 +2 *- 15
15.判断3是数字，不入栈，输出。即为 12 3 +6 2 +2 *- 15 3
15,剩下的所有元素都输出。最终的表达式为 12 3 +6 2 +2 *- 15 3 /-
主要代码：
1.中缀表达式转为后缀表达式
//中缀表达式转为后缀表达式
void TranslateExpress(char str[], char exp[]) {
stack s;
char ch, e{};
int i = 0, j = 0;
InitStack(&s);
ch = str[i++];
while (ch != '\0') {
switch (ch) {
case '(':
Push(&s, ch);//在栈s已经存在的情况下，插入元素ch为新的栈顶元素
break;
case ')':
while (GetTop(s, &e) && e != '(') {//遍历，在栈s已经存在而且非空，返回栈顶的元素e，而且不修改栈顶指针，同时禁止再出现‘（’
Pop(&s, &e);//在栈s已经存在而且非空的情况下，删除s的栈顶元素，并用e返回其值
exp[j++] = e;//继续遍历
}
Pop(&s, &e);
break;
case '+':
case '-':
while (!StackEmpty(s) && GetTop(s, &e) && e != '(') {//注意s应当不是空栈
Pop(&s, &e);
exp[j++] = e;
}
Push(&s, ch);
break;
case '*':
case '/':
while (!StackEmpty(s) && GetTop(s, &e) && e == '/' || e == '*' || e == '^') {
Pop(&s, &e);
exp[j++] = e;
}
Push(&s, ch);
break;
case '^':
while (!StackEmpty(s) && GetTop(s, &e) && e == '^') {
Pop(&s, &e);
exp[j++] = e;
}
Push(&s, ch);
break;
case ' '://中间不允许输入空格
break;
default://出现错误的处理办法
while (ch >= '0' && ch <= '9') {
exp[j++] = ch;
ch = str[i++];
}
i--;
exp[j++] = ' ';
}
ch = str[i++];
}
while (!StackEmpty(s)) {//将剩余的内容全部出栈，此时完成所有的后缀表达式
Pop(&s, &e);
exp[j++] = e;
}
exp[j] = NULL;//确保已经清空栈
2.计算后缀表达式
//计算表达式的值，类型为double是为了防止出现小数导致错误
double ComputeExpress(char a[]) {
opstack s;
int i = 0, value;
float x1, x2, result;
s.top = -1;//一般情况下，栈空时栈顶为-1
while (a[i] != NULL) {
if (a[i] != ' ' && a[i] >= '0' && a[i] <= '9') {
value = 0;
while (a[i] != ' ') {//判断该数为几位数
value = 10 * value + a[i] - '0';//将字符转化为整数进行计算
i++;
}
s.top++;
s.data[s.top] = value;//判断所求数字的具体之后，再入栈，即压入所得数据
}
else {
switch (a[i]) {//进行+，-，*，/ 以及^的运算
case '+':
x1 = s.data[s.top--];
x2 = s.data[s.top--];
result = x1 + x2; //计算x1+x2
s.data[++s.top] = result;//同上，压入所得的数据
break;
case '-':
x1 = s.data[s.top--];
x2 = s.data[s.top--];
result = x2 - x1;
s.data[++s.top] = result;
break;
case '*':
x1 = s.data[s.top--];
x2 = s.data[s.top--];
result = x1 * x2;
s.data[++s.top] = result;
break;
case '/':
x1 = s.data[s.top--];
x2 = s.data[s.top--];
result = x2 / x1;
s.data[++s.top] = result;
break;
case '^':
x1 = s.data[s.top--];
x2 = s.data[s.top--];
result = pow(x2, x1); //pow(a,b)函数表示以a为底数的b次方<数学函数，需要导入math.h头文件>
s.data[++s.top] = result;
break;
}
i++;//继续遍历
}
}
if (!s.top != -1) {
result = s.data[s.top];
s.top--;
if (s.top == -1)
return result;
else { //exit(-1);
printf("----------表达式错误，请重新输入！-----------");
}
}
}
总体代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAXSIZE 50 //顺序栈存储空间的初始分配量
typedef struct {//数字栈结构体
double data[MAXSIZE];
int top;
} opstack;
typedef struct {//符号栈结构体
char data[MAXSIZE];
int top;
} stack;
void InitStack(stack* s) {//构造一个空栈并初始化栈<s为结构体指针>
s->top = 0;
}
int GetTop(stack s, char* e) {//栈顶要单独取出，返回s的栈顶元素，不修改栈顶指针
if (s.top <= 0)
return 0;
else {
*e = s.data[s.top - 1];
return 1;
}
}
bool Pop(stack* s, char* e) {//出栈操作
if (s->top <= 0)//栈空
return false;
else
*e = s->data[--s->top];
return true;
}
bool Push(stack* s, char e) {//入栈操作
if (s->top >= MAXSIZE)
return false;
else
s->data[s->top++] = e;
return true;
}
int StackEmpty(stack s) {//判断栈空
if (s.top == 0)
return true;
else return false;
}
double ComputeExpress(char a[]) {//计算表达式值，类型为double是为了防止出现小数导致错误
opstack s;
int i = 0, value;
float x1, x2, result;
s.top = -1;//一般情况下，栈空时栈顶为-1
while (a[i] != NULL) {
if (a[i] != ' ' && a[i] >= '0' && a[i] <= '9') {
value = 0;
while (a[i] != ' ') {//判断该数为几位数
value = 10 * value + a[i] - '0';//将字符转化为整数进行计算
i++;
}
s.top++;
s.data[s.top] = value;//判断所求数字的具体之后，再入栈，即压入所得数据
}
else {
switch (a[i]) {//进行+，-，*，/ 以及^的运算
case '+':
x1 = s.data[s.top--];
x2 = s.data[s.top--];
result = x1 + x2; //计算x1+x2
s.data[++s.top] = result;//同上，压入所得的数据
break;
case '-':
x1 = s.data[s.top--];
x2 = s.data[s.top--];
result = x2 - x1;
s.data[++s.top] = result;
break;
case '*':
x1 = s.data[s.top--];
x2 = s.data[s.top--];
result = x1 * x2;
s.data[++s.top] = result;
break;
case '/':
x1 = s.data[s.top--];
x2 = s.data[s.top--];
result = x2 / x1;
s.data[++s.top] = result;
break;
case '^':
x1 = s.data[s.top--];
x2 = s.data[s.top--];
result = pow(x2, x1); //pow(a,b)函数表示以a为底数的b次方<数学函数，需要导入math.h头文件>
s.data[++s.top] = result;
break;
}
i++;//继续遍历
}
}
if (!s.top != -1) {
result = s.data[s.top];
s.top--;
if (s.top == -1)
return result;
else { //exit(-1);
printf("----------表达式错误，请重新输入！-----------");
}
}
}
void TranslateExpress(char str[], char exp[]) {//中缀表达式转后缀表达式
stack s;
char ch, e{};
int i = 0, j = 0;
InitStack(&s);
ch = str[i++];
while (ch != '\0') {
switch (ch) {
case '(':
Push(&s, ch);//在栈s已经存在的情况下，插入元素ch为新的栈顶元素
break;
case ')':
while (GetTop(s, &e) && e != '(') {//遍历，在栈s已经存在而且非空，返回栈顶的元素e，而且不修改栈顶指针，同时禁止再出现‘（’
Pop(&s, &e);//在栈s已经存在而且非空的情况下，删除s的栈顶元素，并用e返回其值
exp[j++] = e;//继续遍历
}
Pop(&s, &e);
break;
case '+':
case '-':
while (!StackEmpty(s) && GetTop(s, &e) && e != '(') {//注意s应当不是空栈
Pop(&s, &e);
exp[j++] = e;
}
Push(&s, ch);
break;
case '*':
case '/':
while (!StackEmpty(s) && GetTop(s, &e) && e == '/' || e == '*' || e == '^') {
Pop(&s, &e);
exp[j++] = e;
}
Push(&s, ch);
break;
case '^':
while (!StackEmpty(s) && GetTop(s, &e) && e == '^') {
Pop(&s, &e);
exp[j++] = e;
}
Push(&s, ch);
break;
case ' '://中间不允许输入空格
break;
default://出现错误的处理办法
while (ch >= '0' && ch <= '9') {
exp[j++] = ch;
ch = str[i++];
}
i--;
exp[j++] = ' ';
}
ch = str[i++];
}
while (!StackEmpty(s)) {//将剩余的内容全部出栈，此时完成所有的后缀表达式
Pop(&s, &e);
exp[j++] = e;
}
exp[j] = NULL;//确保已经清空栈
}
bool judge_infix(char str[]) {//判断中缀表达式是否合理
int temp = 0;
if (str[0] == '/' || str[0] == '*')
return false;
if (str[strlen(str) - 1] < '0' && str[strlen(str) - 1]>'9')//strlen()计算给定的字符串长度
return false;
for (int i = 0; i < strlen(str); i++) {
if (str[i] == '(') {
if (i == 0 && (str[i + 1] == '*' || str[i + 1] == '/'))
return false;
else if (str[i - 1] >= '0' && str[i - 1] <= '9')
return false;
temp++;
}
else if (str[i] == ')') {
if (i == 0)
return false;
else if (str[i - 1] == '+' || str[i - 1] == '*' || str[i - 1] == '-' || str[i - 1] == '/')
return false;
else if (str[i + 1] >= '0' && str[i + 1] <= '9')
return false;
temp--;
}
}
if (temp == 0)
return true;
return false;
}
int main() {
char a[MAXSIZE], b[MAXSIZE];
double f;
int flag = 0;
printf("-------------请输入一个计算公式-----------\n");
gets_s(a,100);
printf("-----------------中缀表达式---------------\n%s\n", a);
bool judge = judge_infix(a);
if (judge == false) {
printf("---------计算公式有误，请重新输入！----------\n");
system("pause");
exit(-1);
}
else
TranslateExpress(a, b);
printf("-----------------后缀表达式---------------\n %s\n", b);
f = ComputeExpress(b);
printf("-----------------计算结果-----------------\n %f\n", f);
system("pause");
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
