实验目的：

设计一个顺序栈程序，实现将普通表达式转化为逆波兰表达式，并求值。

实验要求：

1、每个栈元素是一个union类型，例如：

union unData //栈元素的数据类型为Union,Union共用同一块存储空间
{
int d;
char c;
};
提示：union结构体中的变量共用同一个存储空间，即d和c变量的地址码相同

2、顺序栈的类型定义如下：

typedef unData datatype; //栈元素类型，修改为混合型
const int maxsize = 100; //栈容量
typedef struct {
datatype data[maxsize];
int top;
} sqstack; //顺序栈类型
3、自定义输入合法的四则运算表达式

实验运行示例：10-(4+3)/2+5*(1-2)=1.5

image.png

输入
程序启动后，依次input的信息如下：

1、输入一个合法的普通四则运算表达式

输出
完成上述所有输入信息后，程序依次output的信息如下：

1、将普通表达式转化为逆波兰表达式，并输出逆波兰表达式

2、将转化后的逆波兰表达式计算结果，并输出

输入样例 1

8-9*7
输出样例 1

8 9 7 * -
-55
输入样例 2

10-(4+3)/2+5*(1-2)
输出样例 2

10 4 3 + 2 / - 5 1 2 - * +
1.5
代码如下：

#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
union unData             //栈元素的数据类型为Union,Union共用同一块存储空间
{
    int d;
    char c;
};
typedef unData datatype; //栈元素类型，修改为混合型
const int maxsize = 100; //栈容量
typedef struct {
    datatype data[maxsize];
    int top;
} sqstack; 
typedef struct {
    char data[maxsize];
    int top;
} Oper; 
typedef struct {
    double data[maxsize];
    int top;
} Number;
Oper *oper = (Oper*)malloc(sizeof(Oper));
int comPriority(char ch){
	if(ch == '*' || ch == '/'){
		return 1;
	}else if(ch == '+' || ch == '-'){
		return 0;
	}else{
		return -1;
	}
}
bool isOper(char oper){
	return oper == '+' || oper == '-' || oper == '*' || oper == '/' || oper == '(' || oper == ')';
}
void push_stack(sqstack *stack,string str){
	for(size_t i = 0 ; i < str.size(); i++ ){
		stack->data[++stack->top].c = str[i];
	}
	stack->data[++stack->top].c = ' ';
}
//栈的初始化和将中缀表达书转换为后缀表达式的算法
void init_stack(sqstack *stack){
	oper->top = -1;
	stack->top = -1;
	string arr;
	getline(cin , arr);
	char ch, oper1;
	for(size_t i = 0 ; i < arr.size() ; i++){
		ch = arr[i];
		//若读取的是运算符
		if(isOper(ch)){
			//该运算符为左括号"("，则直接存入运算符堆栈。
			if(ch == '('){
				oper->data[++oper->top] = ch;
			}else if(ch == ')'){
				//该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。
				oper1 = oper->data[oper->top--];
				while(oper1 != '('){
					stack->data[++stack->top].c = oper1;
					stack->data[++stack->top].c = ' ';
					oper1 = oper->data[oper->top--];
				}
			}else{
				//若比运算符堆栈栈顶的运算符优先级高，则直接存入运算符堆栈。
				if(comPriority(ch) > comPriority(oper->data[oper->top])){
					oper->data[++oper->top] = ch; 
				}else if(comPriority(ch) <= comPriority(oper->data[oper->top])){
					/*若比运算符堆栈栈顶的运算符优先级低或相等，则不断输出栈顶运算符到操作数堆栈，
					直到栈顶没有运算符的优先级大于或者等于当前预算符（即栈顶存在运算符的话，优先级一定是小于当前运算符），
					最后将当前运算符压入运算符堆栈。
					*/
					char headOper = oper->data[oper->top];
					while(comPriority(headOper) >= comPriority(ch)){
						stack->data[++stack->top].c = headOper;
						stack->data[++stack->top].c = ' ';
						headOper = oper->data[--oper->top];
					}
					oper->data[++oper->top] = ch;
				}
			}
		}else{
			//若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈
			string str = "";
			str.insert(0,1,ch);
			
			while(i + 1 < arr.size() && !isOper(arr[i+1])){
				str.append(1,arr[++i]);
			}
			push_stack(stack,str);
		}
	}
	//当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。
	while(oper->top > -1){
		stack->data[++stack->top].c = oper->data[oper->top--];
		if(oper->top != -1){
			stack->data[++stack->top].c = ' ';
		}
	}
}
void look(sqstack *stack){
	for(int i = 0 ; i <= stack->top ; i++){
		printf("%c",stack->data[i].c);
	}
	printf("\n");
}
double strTransNum(string str){
	  stringstream ss;
      double num;

      ss << str;
      ss >> num;

     return num;
}
double cal(sqstack *stack){
	//定义一个数栈
	Number *number = (Number*)malloc(sizeof(Number));
	number->top = -1;
	double num1,num2;
	char ch;
	for(int i = 0 ; i <= stack->top;){
		ch = stack->data[i++].c;
		if(ch == ' '){
			ch = stack->data[i++].c;
		}
		if(isOper(ch)){
			//如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。
			num2 = number->data[number->top--];
			num1 = number->data[number->top--];
			double value = 0;
			switch(ch){
				case '+':value = num1 + num2;break;
			    case '-':value = num1 - num2;break;
			    case '*':value = num1 * num2;break;
			    case '/':value = num1 / num2;break;
			}
			//将运算结果重新压入堆栈。
			number->data[++number->top] = value;
		}else{
			//如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。
			string str = "";
			str.insert(0,1,ch);
			char newch;
			while(stack->data[i].c >= '0' && stack->data[i].c <= '9' && i <= stack->top){
				newch = stack->data[i++].c;
				str.append(1,newch);
			}
			double d = strTransNum(str);
			number->data[++number->top] = d;
		}
	}
	return number->data[number->top--];

}
int main(){
	sqstack *stack = (sqstack*)malloc(sizeof(sqstack));
	init_stack(stack);
    look(stack);
	cout << cal(stack) <<endl;
	return 0;
}