? ? ? ?常见的四则混合运算表达式，中缀表达式便于人的理解，但后序表达式更方便计算机的运算（如二叉树、堆栈的方法计算）。本文主要谈论的重点是将算术表达式的“中序表达式”转换为“后序表达式”，并根据后序表达式得到算数表达式的值。
一、中序表达式-->后序表达式（堆栈）
1、举例：
2、具体实现的算法步骤（中序->后序（infix->postfix））：
2.1）从左到右读取中序表达式infix_express中的每个字符；
2.2）如果读入的字符为操作数（a~z/A~Z），则直接输出到后序法表达式postfix_express中；
2.3）如果遇到'('，则弹出堆栈内的运算符，知道弹出到一个')'，两者抵消；
?????'('的优先级在堆栈中，比任何运算符都小；但在堆栈外却是优先级最高的运算符；
2.4）将准备进入堆栈中的“外部运算符”与“栈顶的运算符”进行优先级比较，高于则外部运算符压入栈中；低于或等于则将栈中的元素逐个从栈顶弹出，直到外部运算符的优先级高于栈顶的运算符或栈为空时，将外部运算符压入栈；
2.5）读取完中序表达式后，如果堆栈不为空，则将其内部的运算符从栈顶逐个弹出并写在postfix_express的尾部；
注：（部分运算符）在栈中的优先级的排序：'^'、'*'? '/'、'+' '-'、'('等；
3、代码实现：
#include <iostream>
#include<stack> // use std::stack for Stack operations
#include<string>
using namespace std;
/* C++ implementation to convert infix expression to postfix*/
//Function to return precedence of operators
int precede(char c)
{
if (c == '^') { return 3; }
else if (c == '*' || c == '/') { return 2; }
else if (c == '+' || c == '-') { return 1; }
else if (c == '(' ) { return -1; }
else { return -1; }
}
// convert infix expression to postfix expression
string infixToPostfix(string str)
{
std::stack<char> stack_operator; // 用来存放运算符
stack_operator.push('#'); // 栈空的标识符
int len = str.length(); // 输入的中序表达式的长度
string output_postfix; // 用来存放输出的后序表达式postfix
for (int i = 0; i < len; i++)
{
if (str[i] != ' ') // 消除字符串中，空格的影响
{
// If the scanned character is an operand（操作数）, add it to output string
if ((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z'))
{
output_postfix += str[i];
}
// If the scanned character is an '(', push it to the stack
else if (str[i] == '(')
{
stack_operator.push('(');
}
// If the scanned character is an ')', pop and to output string from the stack until an ‘(‘ is encountered.
else if (str[i] == ')')
{
while (stack_operator.top() != '#' && stack_operator.top() != '(')
{
char ch = stack_operator.top();
stack_operator.pop();
output_postfix += ch;
}
// 此种情况是，(一个操作数)，故直接将栈中的'('弹出
if (stack_operator.top() == '(')
{
stack_operator.pop();
}
}
// If an operator is scanned
else
{
while (stack_operator.top() != '#' && precede(str[i]) <= precede(stack_operator.top()))
{
char ch = stack_operator.top();
stack_operator.pop();
output_postfix += ch;
}
stack_operator.push(str[i]);
}
}
}
// Pop all the remaining elements from the stack
while (stack_operator.top() != '#')
{
char ch = stack_operator.top();
stack_operator.pop();
output_postfix += ch;
}
return output_postfix;
}
int main()
{
string infix_express = "a+b*c/h+((d^i)*e+f)*g";
cout << "infix：" << infix_express << endl;
string postfix_express = infixToPostfix(infix_express);
cout << "postfix：" << postfix_express << endl;
return 0;
}二、中序表达式-->后序表达式（二叉树）
待后序学习
三、将中序表达式转换成后序表达式，并计算结果
代码分析：先利用前面提到的将中序表达式转换为后序表达式；接下来，后序表达式可以直接在计算机上运算，使用循环读取表达式中的每个字符并转换成整型压入栈中，当读到运算符时从栈顶pop两个整型数字，运算后重新将结果压入栈中，知道循环结束，输出结果；
#include<iostream>
#include<stack>
#include<string>
using namespace std;
string infixToPostfix(string str)
{
std::stack<char> stack_operator; // 用来存放运算符
stack_operator.push('#'); // 栈空的标识符
int len = str.length(); // 输入的中序表达式的长度
string output_postfix; // 用来存放输出的后序表达式postfix
for (int i = 0; i < len; i++)
{
// If the scanned character is an operand（操作数）, add it to output string
if (str[i] != ' ')
{
if (str[i] >= '0' && str[i] <= '9')
{
output_postfix += str[i];
}
// If the scanned character is an '(', push it to the stack
else if (str[i] == '(')
{
stack_operator.push('(');
}
// If the scanned character is an ')', pop and to output string from the stack until an ‘(‘ is encountered.
else if (str[i] == ')')
{
while (stack_operator.top() != '#' && stack_operator.top() != '(')
{
char ch = stack_operator.top();
stack_operator.pop();
output_postfix += ch;
}
// 此种情况是，(一个操作数)，故直接将栈中的'('弹出
if (stack_operator.top() == '(')
{
stack_operator.pop();
}
}
// If an operator is scanned
else
{
while (stack_operator.top() != '#' && precede(str[i]) <= precede(stack_operator.top()))
{
char ch = stack_operator.top();
stack_operator.pop();
output_postfix += ch;
}
stack_operator.push(str[i]);
}
}
}
// Pop all the remaining elements from the stack
while (stack_operator.top() != '#')
{
char ch = stack_operator.top();
stack_operator.pop();
output_postfix += ch;
}
return output_postfix;
}
int calcPostfix(string str)
{
std::stack<int> stack_operand; // 用来存放操作数
int len = str.length();
for (int i = 0; i < len; i++)
{
if (str[i] != ' ')
{
if (str[i] >= '0' && str[i] <= '9')
{
stack_operand.push((int)str[i] - 48); // 将字符型数字，转换为整型数字
}
else
{
int data1 = stack_operand.top();
stack_operand.pop();
int data2 = stack_operand.top();
stack_operand.pop();
if (str[i] == '+')
{
stack_operand.push(data1 + data2);
}
else if (str[i] == '-')
{
stack_operand.push(data1 - data2);
}
else if (str[i] == '*')
{
stack_operand.push(data1 * data2);
}
else if (str[i] == '/')
{
stack_operand.push((int)data1 / data2);
}
else if (str[i] == '/')
{
stack_operand.push(data1 ^ data2);
}
}
}
}
return stack_operand.top();
}
int main()
{
string infix_express = "2*(3+4) + 5/6";
string postfix_express = infixToPostfix(infix_express);
cout << "postfix：" << postfix_express << endl;
int result = calcPostfix(postfix_express);
cout << result << endl;
}
