博客

中缀表达式转换为后缀表达式

中缀表达式转换为后缀表达式方法

后缀表达式求值

运用后缀表达式进行计算的具体做法：

建立一个栈S 。从左到右读后缀表达式，如果读到操作数就将它压入栈S中，如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符运算，再将运算的结果代替原栈顶的n项，压入栈S中 。如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。

C++代码

#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<map>
using namespace std;
typedef struct node{
	double num;//操作数
	char op;//操作符
	bool flag;//true表示操作数，false表示操作符
}Node;

stack<node> s;//操作符栈
queue<node> q//后缀表达式序列
map<char, int> op;
void change(string str){//将中缀表达式转换为后缀表达式序列
	double number;
	Node temp;
	string::iterator itt = str.begin();
	while (itt != str.end()){
		if ((*itt) == '('){//如果是左括号则压入操作符栈
			temp.flag = false;
			temp.op = (*itt);
			s.push(temp);
			itt++;
			continue;
		}
		if ((*itt) == ')'){//如果是右括号则依次退栈压入队列中直到遇到左括号
			while (s.top().op != '(')
			{
				q.push(s.top());
				s.pop();
			}
			s.pop();//弹出左括号
			itt++;
			continue;
		}
		if ((*itt) >= '0' && (*itt) <= '9'){//如果是数字（注意：操作数可能不止一个，因此需要一位一位读入然后合并在一起
			number = 0;
			temp.flag = true;//标记是操作数
			while (itt!=str.end()&&(*itt) >= '0' && (*itt) <= '9'){
				number = number * 10 + (*itt) - '0';//更新这个数字
				itt++;
			}
			temp.num = number;
			q.push(temp);//将这个操作数压入后缀表达式队列
		}
		else if (s.empty() ||(s.top().op=='(')|| (op[s.top().op] < op[*itt])){//如果操作符栈空或栈顶是左括号或者遇到操作符优先级大于栈顶优先级，则压入栈
			temp.flag = false;//标记为操作符
			temp.op = (*itt);
			s.push(temp);
			itt++;
		}
		else{//如果操作符栈不空且栈顶不是左括号且遇到操作符优先级不大于栈顶优先级，则弹出栈顶元素压入队列
			q.push(s.top());
			s.pop();
		}
		

	}
	while (!s.empty()){//如果操作符栈还有操作符，就把它弹出到后缀表达式队列中
		q.push(s.top());
		s.pop();
	}
}
 double cal(){//计算后缀表达式
	Node temp;
	while (!q.empty()){//后缀表达式非空
		temp = q.front();//记录队首元素
		q.pop();
		if (temp.flag == true){//如果是操作数直接压入栈
			s.push(temp);
		}
		else{//如果是操作符
			double i, j;
			i = s.top().num;//弹出第二个参数
			s.pop();
			j = s.top().num;//弹出第一个参数
			s.pop();
			if (temp.op == '*'){//乘法
				temp.num = i*j;
				s.push(temp);
			}
			if (temp.op == '/'){//除法（注意i,j先后顺序）
				temp.num = j/i;
				s.push(temp);
			}
			if (temp.op == '+'){//加法
				temp.num = i+j;
				s.push(temp);
			}
			if (temp.op == '-'){//减法（注意i,j先后顺序）
				temp.num = j-i;
				s.push(temp);//把该操作数压入栈中
			}
		}
	}
	return s.top().num;//栈顶元素就是后缀表达式的值
}
int main(){
	string str;
	op['+'] = op['-'] = 1;//设定操作符的优先级
	op['*'] = op['/'] = 2;
	while (getline(cin, str), str != "0"){//把表达式的空格去掉
		string::iterator it = str.begin();
		while (it !=str.end()){
			if ((*it) == ' '){
				str.erase(it);
				continue;
			}
			it++;
		}
		while (!s.empty()) s.pop();//初始化栈
		change(str);//将中缀表达式转换为后缀表达式序列
		printf("%.2f\n", cal());//计算后缀表达式的值并输出
		
	}
	return 0;
}