change.cpp

中缀表达式转后缀表达式

#include<conio.h>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
using namespace std;


stack<char> stack_s;//初始化stack，类型为char，stack名为 stack_s
queue<char> queue_t;//初始化queue，类型为char，queue名为 queue_t
char input_s[100]; //存储输入的字符

void input();
void change(char *p);
void output();

void main()
{
int sel;
while(1)
{
	system("cls"); 
	printf("1.中缀表达式转后缀表达式.\n");
	printf("2.输出二叉表达式树.\n");
	printf("3.利用二叉树计算结果.\n");
	printf("0.exit.\n");
	scanf("%d",&sel);
    switch(sel)
	{
    case 1:
		input();
		change(input_s);
		output();
    	getch();
    	break;
    case 2:	
    	getch();
    	break;
    case 3:
    	getch();
    	break;
	}
	if(sel==0) break;
}
}

void input()
{
	cout<<"请输入中缀表达式:";
	scanf("%s",input_s); //输入中缀表达式
}

void change(char *p)
{
		char e;
		int flag=1;//需要用空格隔开数字的标志
		while(*p){
		if(*p>='a'&&*p<='z'||*p>='A'&&*p<='Z'||*p>='0'&&*p<='9')
		{//数字字符或字母进队列T,需要计算结果的输入数字
			if(*p>='0'&&*p<='9'&&flag==1&&*(p+1)>='0'&&*(p+1)<='9')
			{//数字情况
				flag=1;//数字字符是同一个数中的,flag置1
				queue_t.push(*p);
			}
			else
			{//下一个是操作符
				flag=0;//flag置0
				queue_t.push(*p);
				queue_t.push(' ');//进一个完整数字后,空格进队列
			}
		}
		else
		{
			if(*p=='('||*p==')')
			{ //左括号或右括号情况
				if(*p=='(') 
					stack_s.push(*p); //左括号进S栈
				else
				{ //右括号情况,把S栈中的操作符逐个取出进T队,直到S栈顶为左括号
					while(stack_s.top()!='(')
					{
					    queue_t.push(stack_s.top());
						stack_s.pop();
						queue_t.push(' ');
					}
					stack_s.pop();//左括号出S栈
				}
			}
			else
			{//操作符情况
				if(*p=='*'||*p=='/')
				{//优先级高的乘除法
					if(stack_s.empty()||stack_s.top()=='+'||stack_s.top()=='-'||stack_s.top()=='(')
						stack_s.push(*p);//新读入操作符优先级高与栈S顶操作浮或栈S顶为空或栈S顶为左括号,新操作符直接进S栈
					else
					{//新读入操作符优先级与栈S顶操作符相同
						while(!stack_s.empty()&&(stack_s.top()=='*'||stack_s.top()=='/'))
						{//新读入操作符优先级大于S栈顶操作符,S顶操作符出栈,进T队,再和S下一栈顶操作符比较,如此循环
							queue_t.push(stack_s.top());
							stack_s.pop();
						    queue_t.push(' ');
						}
						stack_s.push(*p);//新读入操作符进S栈
					}
				}
				else
				{//优先级低的加减法
					if(stack_s.empty()||stack_s.top()=='(') stack_s.push(*p);//栈S顶为空或栈S顶为左括号,新操作符直接进S栈
					else
					{//S栈顶操作符和新读入操作符优先级相等，或S栈顶操作符优先级较高
						while(!stack_s.empty()&&((stack_s.top()=='+'||stack_s.top()=='-')||(stack_s.top()=='*'||stack_s.top()=='/')))
						{//新读入操作符优先级小于或等于S栈顶操作符，,S顶操作符出栈,进T队,再和S下一栈顶操作符比较,如此循环
						    queue_t.push(stack_s.top());
							stack_s.pop();
						    queue_t.push(' ');
						}
			            stack_s.push(*p);//新读入操作符进S栈
					}
				}
			}
			flag=1;
		}
		++p;//找到下一字符
	}
	while(!stack_s.empty())
	{//S栈非空则把栈顶元素取出，进T队
		queue_t.push(stack_s.top());
		stack_s.pop();
		queue_t.push(' ');
	}
}

void output()
{
	cout<<"后缀表达式为:";
	while(!queue_t.empty()) 
	{
		cout<<queue_t.front();
		queue_t.pop();
	}
	cout<<endl;
}