中缀表达式转前缀和后缀表达式

  1. #ifndef POSTFIX_TO_NIFIXEXPRESS_H
  2. #define POSTFIX_TO_NIFIXEXPRESS_H
  3. #include<iostream>
  4. #include<string>
  5. #include<stack>
  6. /************************************************************************/
  7. /*				中缀表达式转前缀表达式
  8. 建立一个栈来保存运算符，和一个字符容器存字符及运算符的输出。
  9. 从后向前扫描中缀表达式：
  10. 1、如果遇到的是普通字符那么存入容器中
  11. 2、如果遇到的是‘）’，存入容器中
  12. 3、如果遇到的是运算符(大于等于栈顶的优先级就入栈，否则弹栈)
  13. 	如果当前栈为空或者当前运算符的优先级大于等于栈顶元素的优先级，那么入栈。
  14. 	如果栈顶元素是‘）’，还是入栈。
  15. 	如果当前运算符的优先级小于栈顶元素的优先级，那么弹栈存入容器中，一直到栈顶元素为‘）’或
  16. 	者当前运算符的优先级大于或者等于栈顶元素的优先级。将当前运算符入栈。
  17. 4、如果遇到‘（’，那么弹栈存入容器一直遇到到‘）’，将‘）’弹出
  18. 5、返向输出容器中的字符
  19. */
  20. /************************************************************************/
  21. std::string  nifixExpressToPrefix(std::string &nifixExp){
  22. 	std::stack<char> operStack; 
  23. 	std::string prefixExp; 
  24. 	for(auto iter=nifixExp.rbegin(); iter!=nifixExp.rend(); iter++){
  25. 		if(*iter!='*'&&*iter!='\'&&*iter!='+'&&*iter!='-'&&*iter!='('&&*iter!=')'){
  26. 			prefixExp.push_back(*iter);
  27. 		}else if(*iter==')'){
  28. 			operStack.push(*iter); 
  29. 		}else if(*iter=='('){
  30. 			while(operStack.top()!=')'){
  31. 				prefixExp.push_back(operStack.top()); 
  32. 				operStack.pop(); 
  33. 			}
  34. 			operStack.pop(); 
  35. 		}else if(*iter=='*'||*iter=='\'){
  37. 			operStack.push(*iter); 
  39. 		}else if(*iter=='+'||*iter=='-'){
  40. 			if(operStack.empty()){
  41. 				operStack.push(*iter); 
  42. 			}else{
  43. 				if(operStack.top()=='-'||operStack.top()=='+'||operStack.top()==')'){
  44. 					operStack.push(*iter); 
  45. 				}else{
  46. 					while(!operStack.empty()){
  47. 						if(operStack.top()==')'||operStack.top()=='+'||operStack.top()=='-'){
  48. 							break;
  49. 						}
  50. 						prefixExp.push_back(operStack.top()); 
  51. 						operStack.pop(); 
  52. 					}
  53. 					operStack.push(*iter); 
  54. 				}
  55. 			}
  56. 		}
  57. 	}
  58. 	while(!operStack.empty()){
  59. 		prefixExp.push_back(operStack.top()); 
  60. 		operStack.pop();
  61. 	}
  62. 	std::string strResult; 
  63. 	for(auto iter=prefixExp.rbegin(); iter!=prefixExp.rend(); iter++){
  64. 		strResult.push_back(*iter); 
  65. 	}
  66. 	return strResult; 
  67. 	
  68. }
  70. #endif

  1. #ifndef NIFIX_TO_POSTFIX_H
  2. #define NIFIX_TO_POSTFIX_H
  3. #include<iostream>
  4. #include<string>
  5. #include<stack>
  6. /************************************************************************/
  7. 		
  8. /*			中缀表达式转后缀表达式
  10. 建立一个运算符的栈，从左向右开始扫描中缀表达式。
  11. 1、如果是字符则直接输出
  12. 2、如果是‘（’，那么入栈。
  13. 3、如果是运算符：（大于栈顶的优先级就入栈，否则弹栈）
  14.    如果栈顶的元素是‘（’或者当前运算符的优先级比栈顶元素优先级高，那么入栈。
  15.    如果当前的运算符的优先级比栈顶的优先级低或者相等，那么就弹栈输出，一直输出到栈顶的运算符
  16.    的优先级比当前运算符优先级低或者栈为空，以及栈顶为'('。将当前的运算符压入栈。
  17. 4、如果是‘）’，那么一直弹栈输出，一直弹到第一次看到‘（’
  19. */
  20. /************************************************************************/
  21. std::string nifixToPostfix(const std::string &nifixExp){
  22. 	std::stack<char> operaStack; 
  23. 	std::string postfixStr; 
  24. 	for(auto iter=nifixExp.begin(); iter!=nifixExp.end(); iter++){
  25. 		if(*iter!='*'&&*iter!='\'&&*iter!='+'&&*iter!='-'&&*iter!='('&&*iter!=')'){
  26. 				postfixStr.push_back(*iter); 
  27. 		}else if(*iter=='('){
  28. 			operaStack.push('('); 
  29. 		}else if(*iter==')'){
  30. 			while(operaStack.top()!='('){
  31. 				postfixStr.push_back(operaStack.top()); 
  32. 				operaStack.pop(); 
  33. 			}
  34. 			operaStack.pop(); 
  35. 		}else if(*iter=='*'||*iter=='\'){
  36. 			if(operaStack.empty()){
  37. 				operaStack.push(*iter); 
  38. 			}else{
  39. 				if(operaStack.top()=='+'||operaStack.top()=='-'||operaStack.top()=='('){
  40. 					operaStack.push(*iter); 
  41. 				}else{
  42. 					while(!operaStack.empty()){
  43. 						if(operaStack.top()=='('||operaStack.top()=='+'||operaStack.top()=='-'){
  44. 							break;
  45. 						}
  46. 						postfixStr.push_back(operaStack.top()); 
  47. 						operaStack.pop(); 
  48. 					}
  49. 					operaStack.push(*iter); 
  50. 				}
  51. 			}
  52. 		}else if(*iter=='+'||*iter=='-'){
  53. 			if(operaStack.empty()){
  54. 				operaStack.push(*iter); 
  55. 			}else{
  56. 				while(!operaStack.empty()){
  57. 					if(operaStack.top()=='('){
  58. 						break;
  59. 					}
  60. 					postfixStr.push_back(operaStack.top()); 
  61. 					operaStack.pop();
  62. 				}
  63. 				operaStack.push(*iter); 
  64. 			}
  65. 		}
  66. 	}
  67. 	while(!operaStack.empty()){
  68. 		postfixStr.push_back(operaStack.top()); 
  69. 		operaStack.pop(); 
  70. 	}
  71. 	return postfixStr; 
  72. }
  74. #endif










【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yml435/p/4784293.html