c语言的数据结构表达式求值

article/2025/9/15 16:17:01

最近学习c语言的数据结构中有关栈的实现。下面是用栈实现表达式求值的一个实例，用的是顺序栈的形式
原理：

List item

我们默认一‘#’开始，最后输入’#‘结束

在运算中的每一步中，任意两个相继出现的算符theta1和theta2之间的关系，至多只有三种关系：
1,theta1<theta2
2,theta1>theta2
3,theta1=theta2
theta1和theta2之间的关系由下表给出
在这里插入图片描述

根据算数运算规则的左结合性，先压入栈的同型号运算符优先级要大些，比如栈顶为‘+’，输入为‘+’，此时该算那个‘+’呢，应该算栈顶那个‘+’；
因为我们无法比较（和#，（，#，）之间的优先级关系所以如果输入这种运算符的话程序将会出错，所以在程序中应注意避免
算法：
该算法把数字和字符都以char型入栈
1）初始化opnd（数字）和optr（字符）栈，将#压入oper栈
2）循环表达式如果输入的值ch非#和栈顶元素非#则执行以下操作：
若输入的值不是运算符，则压入opnd（数字）栈
否则将输入的值与栈顶进行比较
若是<则ch压入optr栈，读入下一字符
若是>则optr弹出运算符，opnd弹出两个元素，和运算符进行运算
若是=则optr栈顶元素是(且ch是），弹出optr栈顶，相当于括号匹配成功
3）最后循环结束opnd栈顶元素即为所求值
以下是源代码，所用软件是visualstudio2022

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include"pch.h"#define STACK_CHAR_SIZE 100
#define STACKINCREMENT 10typedef struct {char* base;char* top;int stacksize;
}SqStack;//获取theta所对应的索引
//返回索引值
int getIndex(char theta)   
{int index = -1;switch (theta){case '+':index = 0;break;case '-':index = 1;break;case '*':index = 2;break;case '/':index = 3;break;case '(':index = 4;break;case ')':index = 5;break;case '#':index = 6;default:break;}return index;
}
//输入索引值
//返回优先级关系
char getPriority(char theta1, char theta2)   //获取theta1与theta2之间的优先级  
{const char priority[][7] =     //算符间的优先级关系  {{ '>', '>', '<', '<', '<', '>', '>' },{ '>', '>', '<', '<', '<', '>', '>' },{ '>', '>', '>', '>', '<', '>', '>' },{ '>', '>', '>', '>', '<', '>', '>' },{ '<', '<', '<', '<', '<', '=', '0' },{ '>', '>', '>', '>', '0', '>', '>' },{ '<', '<', '<', '<', '<', '0', '=' },};int index1 = getIndex(theta1);int index2 = getIndex(theta2);return priority[index1][index2];
}//初始化栈
bool InitStack(SqStack&S)
{S.base = NULL;S.base = (char*)malloc(sizeof(char)*STACK_CHAR_SIZE);if (!S.base){return false;}S.top = S.base;S.stacksize = STACK_CHAR_SIZE;return true;}int DestoryStack(SqStack& S) {if (S.base == NULL) exit(1);free(S.base);S.base = NULL;return true;
}int ClearStack(SqStack& S)
{if (S.base == NULL)exit(1);S.top = S.base;return true;
}char GetTop(SqStack& S) {if (S.top != S.base) return *(S.top - 1);
}bool Push(SqStack& S, char e) {if (S.top - S.base == S.stacksize){return false;}*S.top++ = e;return true;
}char Pop(SqStack& S, char& e) {if (S.top == S.base) return false;e = *--S.top;return true;
}//输入操作数aa，操作符theta，操作数bb
//输出操作后结果
char Operate(char aa, char theta, char bb)
{int a = aa-'0';//将字符型数字转换成int型int b = bb-'0';int res = 0;switch (theta){case '+':res = a + b;break;case '-':res = a - b;break;case '*':res = a * b;break;case '/':res = a / b;break;default:break;}return res+'0';
}
int main()
{SqStack opnd, optr;//初始化运算符栈optr，操作数栈opndchar ch,flag2,theta,a,b,x;int flag1,res;InitStack(opnd); InitStack(optr);//初始化Push(optr, '#');printf("请输入表达式: ");scanf(" %c", &ch);//在ch不为#或者optr栈顶不为#时循环while (ch != '#'||GetTop(optr) != '#'){//如果ch为数字就插入opnd栈//判断是否为数字用的是函数getIndexflag1= getIndex(ch);if (flag1 < 0 || flag1>6) { Push(opnd, ch); printf("请输入表达式: "); scanf(" %c", &ch); }else{//比较ch和optr栈顶元素的优先级,返回>,<或者=flag2 = getPriority(GetTop(optr), ch);switch (flag2){case '<'://小于压入optr栈，再读chPush(optr, ch); printf("请输入表达式: ");scanf(" %c", &ch);break;case'>'://大于弹出optr栈顶元素，将opnd元素依次弹出两个求值再压入Pop(optr, theta);//弹出栈顶，用theta接受栈顶元素Pop(opnd, a); Pop(opnd, b);Push(opnd,Operate(b,theta,a));//求值,并压入,这里体现栈的特性先进后出，计算时要注意break;case'='://当等于的时候意味这optr中栈顶左括号和ch（此时为右括号）相遇，此时要将左括号弹出意味着完成括号内的运算Pop(optr, x); printf("请输入表达式: ");scanf(" %c", &ch);break;}}}res = GetTop(opnd) - '0';//循环完成后opnd栈顶即为结果，不过此时是字符型，减去字符0即可printf("结果是%d ", res);DestoryStack(opnd); DestoryStack(optr);
}