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

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

1. List item

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

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

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

#include
#include
#include
#include"pch.h"

#define STACK_CHAR_SIZE 100
#define STACKINCREMENT 10

typedef 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，操作数栈opnd
	char 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栈
		//判断是否为数字用的是函数getIndex
		flag1= 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栈，再读ch
				Push(optr, ch); printf("请输入表达式: ");scanf(" %c", &ch);
				break;
			case'>'://大于d出optr栈顶元素，将opnd元素依次d出两个求值再压入
				Pop(optr, theta);//d出栈顶，用theta接受栈顶元素
				Pop(opnd, a); Pop(opnd, b);
				Push(opnd,Operate(b,theta,a));//求值,并压入,这里体现栈的特性先进后出，计算时要注意
				break;
			case'='://当等于的时候意味这optr中栈顶左括号和ch（此时为右括号）相遇，此时要将左括号d出意味着完成括号内的运算
				Pop(optr, x); printf("请输入表达式: ");scanf(" %c", &ch);
				break;
			}
		}
		
	}res = GetTop(opnd) - '0';//循环完成后opnd栈顶即为结果，不过此时是字符型，减去字符0即可
	printf("结果是%d ", res);
	DestoryStack(opnd); DestoryStack(optr);
}

测试结果