【栈的应用】中缀表达式转后缀以及后缀表达式的计算

【栈的应用】中缀表达式转后缀以及后缀表达式的计算 中缀表达式转后缀

解题思路:
1.数字不用进行处理直接进行输出即可
2.字符需要考虑加减乘除的优先级
3.左括号与右括号的考虑
4.栈为空以及栈顶元素的考虑

typedef struct stack
{
	char nums[20];
	int top;
}stack, * pstack;
void init(pstack s)
{
	memset(s->nums, 0, sizeof(s->nums));
	s->top = -1;
}
void push(pstack s, char ch)
{
	s->nums[++s->top] = ch;
}
void pop(pstack s)
{
	s->top--;
}
char gettop(pstack s)
{
	return s->nums[s->top];
}
char* zhuanhua(pstack s, char* str)
{
	int len = strlen(str);
	int i;
	int index = 0;
	char* ret = (char*)malloc(sizeof(char) * 20);
	for (i = 0; i < len; ++i)
	{
		//若为数字则直接放入接受的字符组
		if (str[i] <= '9' && str[i] >= '0')
		{
			ret[index++] = str[i];
		}
		//若为运算符
		else
		{
			//当前元素为乘除时
			if (str[i] == '*' || str[i] == '/')
			{
			//若栈不为空且栈顶元素为+-则输出栈内所有元素
				while (s->top > +0 && gettop(s) == '+' || gettop(s) == '-')
				{
					ret[index++] = gettop(s);
					pop(s);
				 }
				 //将当前元素入栈
				push(s, str[i]);
			}
			//若当前元素为+-
			else if (str[i] == '+' || str[i] == '-')
			{
			//当栈顶不为左括号且栈不为空时输出所有元素
				while (gettop(s) != '(' && s->top >= 0)
				{
					ret[index++] = gettop(s);
					pop(s);
				}
				push(s, str[i]);
			}
			//当前元素为做括号则直接入栈
			else if (str[i] == '(')
			{
				push(s, str[i]);
			}
			//若为右括号则不断输出直到遇到左括号停止
			else if (str[i] == ')')
			{
				while (gettop(s) != '(')
				{
					ret[index++] = gettop(s);
					pop(s);
				}
				pop(s);
			}

		}
	}
	//将栈内剩余元素输出
	while (s->top != -1)
	{
		ret[index++] = gettop(s);
		pop(s);
	}
	ret[index] = '';
	return ret;
}
int main()
{
	stack s;
	init(&s);
	char str[25] = "3*(5+6)-2";
	char* q = zhuanhua(&s, str);
	printf("%s", q);
	return 0;
}

后缀表达式的计算

解题思路:

1.每两个数字和一个运算符一算
2.和上面的中缀转后缀很像，不过这里是用栈存储数字，上面使用栈存储字符.

typedef struct stack
{
	int nums[20];
	int top;
}stack, * pstack;
void init(pstack s)
{
	memset(s->nums, 0, sizeof(s->nums));
	s->top = -1;
}
void push(pstack s, char ch)
{
	s->nums[++s->top] = ch;
}
void pop(pstack s)
{
	s->top--;
}
int gettop(pstack s)
{
	return s->nums[s->top];
}
void jisuan(pstack s, char* str)
{
	int len = strlen(str);
	int i;
	for (int i = 0; i < len; ++i)
	{ 
		if (str[i] <= '9' && str[i] >= '0')
			s->nums[++s->top] = str[i] - '0';
		else
		{
			int a = s->nums[s->top--];
			int b = s->nums[s->top--];
			if (str[i] == '+')
			{
				push(s, b + a);
			}
			else if (str[i] == '-')
				push(s, b - a);
			else if (str[i] == '*')
				push(s, b * a);
			else
				push(s, b / a);
		}
	}
}

int main()
{
	stack s;
	init(&s);
	char str[25] = "356+*2-";
	jisuan(&s, str);
	printf("%d", s.nums[s.top]);
	return 0;
}

两个栈合成一个队列

解题思路:

• 两个栈分管入队与出队 *** 作，一个栈负责入队，一个栈负责出队
• 栈是先进后出的结构，我们使入队的那个栈的元素出栈到出队的栈中，再从出队的栈中出栈即可形成与队列一样的效果.

typedef struct stack
{
	int nums[20];
	int top;
}stack,*pstack;
void init(pstack s)
{
	memset(s->nums, 0, sizeof(s->nums));
	s->top = -1;
}
void push(pstack s,int val)
{
	s->nums[++s->top] = val;
}
void pop(pstack s)
{
	--s->top;
}
int gettop(pstack s)
{
	return s->nums[s->top];
}
bool empty(pstack s)
{
	return s->top == -1;
}
void rudui(pstack s,int val)
{
	s->nums[++s->top] = val;
}
void chudui(pstack s1,pstack s2)
{
	while(!empty(s2))
	{
		printf("%d ", gettop(s2));
		pop(s2);
	}
	while (!empty(s1))
	{
		push(s2, gettop(s1));
		pop(s1);
	}
	while (!empty(s2))
	{
		printf("%d ", gettop(s2));
		pop(s2);
	}
	return;

}
int main()
{
	stack s1, s2;
	init(&s1);
	init(&s2);
	push(&s2, 10);
	en_push(&s1, 1);
	en_push(&s1, 2);
	en_push(&s1, 3);
	en_push(&s1, 4);
	en_push(&s1, 5);
	traverse(&s1, &s2);
	return 0;
}