[C++知识库]中缀表达式到逆波兰表达式并计算结果（c语言版）

中缀表达式到逆波兰表达式并计算结果（c语言版）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "括号匹配.h"

//处理表达式相关代码

typedef struct BKNode
{
	char data;
	struct BKNode* next;
}BKNode,*BKStack;


typedef struct DTNode
{
	int data;
	struct DTNode* next;
}DTNode,*DTStack;



bool Init_TwoStack(BKStack &B,DTStack &D) 
{
	B = (BKNode*)malloc(sizeof(BKNode));
	D = (DTNode*)malloc(sizeof(DTNode));
	B->next = NULL;
	D->next = NULL;
	if (B == NULL || D == NULL) 
	{
		return false;
	}
	return true;
}


bool IsEmpty_BKStack(BKStack B)
{
	return B->next == NULL;
}


bool IsEmpty_DTStack(DTStack D)
{
	return D->next == NULL;
}

bool Push_BKStack(BKStack &B,char c)
{
	BKNode* node = (BKNode*)malloc(sizeof(BKNode));
	if (node == NULL) 
	{
		return false;
	}
	node->data = c;
	node->next = B->next;
	B->next = node;
	return true;
}

bool Push_DTStack(DTStack &D, int c)
{
	DTNode* node = (DTNode*)malloc(sizeof(DTNode));
	if (node == NULL)
	{
		return false;
	}
	node->data = c;
	node->next = D->next;
	D->next = node;
	return true;
}

bool Pop_BKStack(BKStack &B,char &e)
{
	if (IsEmpty_BKStack(B)) 
	{
		return false;
	}
	BKNode* n = B->next;
	e = n->data;
	B->next = n->next;
	free(n);
	return true;
}


bool Pop_DTStack(DTStack &D, int &e)
{
	if (IsEmpty_DTStack(D))
	{
		return false;
	}
	DTNode* n = D->next;
	e = n->data;
	D->next = n->next;
	free(n);
	return true;
}

bool GetTop_BKStack(BKStack B,char &e) 
{
	if (IsEmpty_BKStack(B)) 
	{
		return false;
	}
	e = B->next->data;
	return true;
}


bool GetTop_DTStack(DTStack D, char &e)
{
	if (IsEmpty_DTStack(D))
	{
		return false;
	}
	e = D->next->data;
	return true;
}


bool IsOperator(char c) 
{
	return ((c == '+') || (c == '-') || (c == '*') || (c == '/'));
}

bool IsBlacket(char c) 
{
	return ((c == '(') || (c == ')'));
}

bool IsNumber(char c) 
{
	return (!IsOperator(c) && !IsBlacket(c));
}



int SimpleCalc(char c, int num1, int num2)
{
	int result;
	switch (c)
	{
	case '+':
		result = num1 + num2;
		break;
	case '-':
		result = num1 - num2;
		break;
	case '*':
		result = num1 * num2;
		break;
	case '/':
		result = num1 / num2;
		break;
	}
	return result;
}


void Calc(DTStack &D,char c) 
{
	int num1;
	int num2;
	Pop_DTStack(D, num2);
	Pop_DTStack(D, num1);

	int result= SimpleCalc(c, num1, num2);

	Push_DTStack(D, result);
}


bool ConvertCharSToNum(char* str, int i, int len, int &re)
{
	char nums[9];
	int offset = 0;
	bool flag = false;
	while (IsNumber(str[i + offset]))
	{
		if (i - 1 >= 0)
		{
			if (IsNumber(str[i - 1]))
			{
				flag = false;
				break;
			}
		}
		if (i + offset >= len)
		{
			break;
		}
		nums[offset] = str[i + offset];
		flag = true;
		offset++;
	}
	if (flag)
	{
		re = strtol(nums, NULL, 10);
		return true;
	}

	return false;
}


int Compute(char* str,int len) 
{
	BKStack B;
	DTStack D;
	Init_TwoStack(B, D);

	
	
	for (int i = 0; i < len; i++)
	{
		char c = str[i];
		if (IsNumber(c)) 
		{
			int num;
			if (ConvertCharSToNum(str, i, len, num)) 
			{
				printf("%d\t", num);
				Push_DTStack(D, num);
			}
			
		}

		if (IsOperator(c)) 
		{
			char opb;
			if (!GetTop_BKStack(B,opb)) 
			{
				Push_BKStack(B, c);
			}
			else
			{
				
				while (false == ((opb == '+' || opb == '-') && (c == '/' || c == '*')))
				{
					if (opb == '(') 
					{
						break;
					}

					bool popSuc= Pop_BKStack(B, opb);
					if (!popSuc)
					{
						break;
					}

					//cal
					Calc(D, opb);
					if (!GetTop_BKStack(B, opb)) 
					{
						opb = NULL;
					}
				}
				
				Push_BKStack(B, c);
				
			}

		}

		if (IsBlacket(c)) 
		{
			if (c == '(') 
			{
				Push_BKStack(B, c);
			}
			else
			{
				
				while (true)
				{
					char kh;
					Pop_BKStack(B, kh);
					if (kh == '(')
					{
						break;
					}
					//cal
					Calc(D, kh);
					
				}
				
				
				
			}
			
		}

	}


	char cl;
	while (Pop_BKStack(B,cl))
	{
		Calc(D, cl);
	}

	int result;
	Pop_DTStack(D, result);
	return result;
}


void testStrtol(char* str,int len) 
{
	for (int i = 0; i < len; i++)
	{
		int re;
		if (ConvertCharSToNum(str, i, len, re)) 
		{
			printf("%d\n", re);
		}
	}
}



int main() 
{
	printf("Input your Expression:\n");
	char str[300] ; //= "31*2+((778+322)/5+100)*2"  //=2*(5+5)+31*(2-1)+((778+322)/5+100)*2
	scanf_s("%s", str,300);
	int len = strlen(str);
	if (!BracketsMatch(str, len)) 
	{
		printf("brackets not match!!\n");
		return -1;
	}
	else
	{
		printf("brackets match success :)\n");
	}
	
	//testStrtol(str, len);
	int re= Compute(str, len);
	printf("\n");
	printf("result is: %d", re);
	return 0;
}

#include<stdio.h>
#include<stdlib.h>

#define MaxSize 100

![在这里插入图片描述](https://img-blog.csdnimg.cn/e3c649d2fb254850a90d1a1c3cfa27b9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAaGFpcmVuYWE=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center)
//匹配括号相关代码

typedef struct 
{
	char data[MaxSize];
	int top;
}  Sq1Stack;


bool Init_Sq1Stack(Sq1Stack &S) 
{
	S.top = -1;
	return true;
}


bool IsEmpty_Sq1Stack(Sq1Stack S) 
{
	return S.top ==-1;
}


bool Push_Sq1Stack(Sq1Stack &S,char c) 
{
	if (S.top >= MaxSize-1) 
	{
		return false;
	}
	S.data[++S.top] = c;
	return true;
}


bool Pop_Sq1Stack(Sq1Stack &S,char &c) 
{
	if (IsEmpty_Sq1Stack(S)) 
	{
		return false;
	}

	c = S.data[S.top--];
	return true;
}




//
//int test() 
//{
//	Sq1Stack S;
//	Init_Sq1Stack(S);
//	for (int i = 0; i < 10; i++)
//	{
//		Push_SqStack(S, i);
//	}
//
//	int e=-1;
//	while (Pop_Sq1Stack(S,e))
//	{
//		printf("%d\t", e);
//		e = -1;
//	}
//	printf("\n");
//
//	return 0;
//
//}
//


bool BracketsMatch(char* str,int len) 
{
	Sq1Stack S;
	Init_Sq1Stack(S);



	for (int i = 0; i < len; i++)
	{
	

		char s = str[i];
		if (s=='('||s=='['||s=='{')
		{
			Push_Sq1Stack(S, s);
		}
		else if(s==')'||s==']'||s=='}')
		{
			if (IsEmpty_Sq1Stack(S)) 
			{
				return false;
			}

			char c;
			Pop_Sq1Stack(S, c);
			if ((s == ')'&& c != '(') || (s == ']'&&c != '[') || (s == '}'&&c != '{'))
			{
				return false;
			}
			
			
			
		}

	}

	return IsEmpty_Sq1Stack(S);
}


int main_BlacketMatch() 
{
	char str[] = "((){}{}[{{}}()(]()))";  //
	int len = sizeof(str) / sizeof(str[0])-1; //尾部有\0多一个字符
	bool b = BracketsMatch(str,len);
	if (b)
		printf("%s", "match success!!");
	else
		printf("%s", "match failed!!");
	return 0;
}

最终结果