前缀表达式和后缀表达式 – C++代码

大家好，欢迎来到IT知识分享网。

刷题向文章，不介绍原理，只介绍规则

速览

算术表达式分为：

• 前缀表达式(波兰式)
• 后缀表达式(逆波兰式)
• 中缀表达式

中缀表达式是我们最熟悉的表达式，是常见的运算式，如下所示：

(2 + 3) * 4 - 5 

- * + 2 3 4 5 

注意，并不是所有运算符在所有数字之前，如：

+ - 1 2 * 3 5 

也可以是前缀表达式

前缀表达式

前缀表达式的运算规则

例：计算前缀表达式 – * +2345 的值

前缀表达式的值为 15

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

创建2个空栈 S1 和 S2，S1 为符号栈，S2 为临时栈，从右向左扫描中缀表达式

1. 如果遇到数字，压入 S2 栈中
2. 如果遇到符号：
   如果 S1 为空栈，或者 S1 栈顶为右括号，直接压入 S1 中
   如果扫描到的符号优先级大于等于 S1 栈顶的符号，直接压入 S1 中
   如果扫描到的符号优先级小于 S1 栈顶的符号，则把 S1 栈顶的符号弹出并压入 S2，重复这一步骤，直到可以把扫描到的符号压入 S1
   
   
   
3. 如果遇到括号：
   如果遇到左括号，直接压入 S1
   如果遇到右括号，依次弹出 S1 栈顶的符号并压入 S2，直到遇到左括号时，丢弃这一对括号
   最后，依次把 S1 栈顶元素弹出压入 S2 中，依次弹出 S2 栈顶元素，得到前缀表达式
   
   
   

例：把中缀表达式 1+((2+3) * 4)-5 转换为前缀表达式

所求前缀表达式为：-+1*+2345

代码实现：

// 前缀表达式练习 - 只能输入 0-9 的数 #include<iostream> using std::cin; using std::cout; using std::endl; #include<string> using std::string; #include<stack> using std::stack; bool isoperator(int _C); bool isbrackets(int _C); int main(int argc, char*argv[]) { 
     // 输入中缀表达式 string infix; cin >> infix; // 中缀表达式 => 前缀表达式 stack<char>S1, S2; for (auto it = infix.crbegin(); it != infix.crend(); it++) { 
     if (isdigit(*it))S2.push(*it); else if (isoperator(*it)) { 
     CASE_ISOPERATOR: if (S1.empty() || ')' == S1.top())S1.push(*it); else if ('+' == S1.top() || '-' == S1.top())S1.push(*it); else if ('*' == *it || '/' == *it)S1.push(*it); else { 
     S2.push(S1.top()); S1.pop(); goto CASE_ISOPERATOR; } } else if (isbrackets(*it)) { 
     if (')' == *it)S1.push(*it); else { 
     while (!isbrackets(S1.top())) { 
     S2.push(S1.top()); S1.pop(); } S1.pop(); } } } while (!S1.empty()) { 
     S2.push(S1.top()); S1.pop(); } string prefix; while (!S2.empty()) { 
     prefix.push_back(S2.top()); S2.pop(); } // 计算前缀表达式的值 stack<int>value; for (auto it = prefix.crbegin(); it != prefix.crend(); it++) { 
     if (isdigit(*it))value.push(*it - '0'); else { 
     int top, second_top; top = value.top(); value.pop(); second_top = value.top(); value.pop(); switch (*it) { 
     case'+':value.push(top + second_top); break; case'-':value.push(top - second_top); break; case'*':value.push(top*second_top); break; case'/':value.push(top / second_top); break; } } } // 输出前缀表达式及其值 cout << prefix << '=' << value.top() << endl; return 0; } bool isoperator(int _C) { 
     return '+' == _C || '-' == _C || '*' == _C || '/' == _C ? true : false; } bool isbrackets(int _C) { 
     return '(' == _C || ')' == _C ? true : false; } 

后缀表达式

后缀表达式的运算

例：计算后缀表达式 23+4 * 5- 的值

后缀表达式的值为 15

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

创建2个空栈 S1 和 S2，S1 为符号栈，S2 为临时栈，从左向右扫描中缀表达式

1. 如果遇到数字，压入 S2 栈中
2. 如果遇到符号：
   如果 S1 为空栈，或者 S1 栈顶为左括号，直接压入 S1 中
   如果扫描到的符号优先级大于 S1 栈顶的符号，直接压入 S1 中
   (注意前缀表达式是大于等于，而后缀表达式只有大于才可以直接压入)
   如果扫描到的符号优先级小于 S1 栈顶的符号，则把 S1 栈顶的符号弹出并压入 S2，重复这一步骤，直到可以把扫描到的符号压入 S1
   
   
   
   
3. 如果遇到括号：
   如果遇到右括号，直接压入 S1
   如果遇到左括号，依次弹出S1栈顶的符号并压入 S2，直到遇到左括号时，丢弃这一对括号
   最后，依次把 S1 栈顶元素弹出压入 S2 中，依次弹出 S2 栈顶元素，“反向输出”，得到前缀表达式
   
   
   

例：把中缀表达式 1+((2+3) * 4)-5 转换为前缀表达式

所求后缀表达式为：1 2 3+4*+5-

代码实现：

// 后缀表达式练习 - 只能输入 0-9 的数 #include<iostream> using std::cin; using std::cout; using std::endl; #include<string> using std::string; #include<stack> using std::stack; bool isoperator(int _C); bool isbrackets(int _C); int main(int argc, char*argv[]) { 
     // 输入中缀表达式 string infix; cin >> infix; // 中缀表达式 => 后缀表达式 stack<char>S1, S2; for (auto it = infix.cbegin(); it != infix.cend(); it++) { 
     if (isdigit(*it))S2.push(*it); else if (isoperator(*it)) { 
     CASE_ISOPERATOR: if (S1.empty() || '(' == S1.top())S1.push(*it); else if (('+' == S1.top() || '-' == S1.top()) && ('*' == *it || '/' == *it))S1.push(*it); else { 
     S2.push(S1.top()); S1.pop(); goto CASE_ISOPERATOR; } } else if (isbrackets(*it)) { 
     if ('(' == *it)S1.push(*it); else { 
     while (!isbrackets(S1.top())) { 
     S2.push(S1.top()); S1.pop(); } S1.pop(); } } } while (!S1.empty()) { 
     S2.push(S1.top()); S1.pop(); } string prefix; while (!S2.empty()) { 
     prefix.insert(prefix.begin(), S2.top()); S2.pop(); } // 计算后缀表达式的值 stack<int>value; for (auto it = prefix.cbegin(); it != prefix.cend(); it++) { 
     if (isdigit(*it))value.push(*it - '0'); else { 
     int top, second_top; top = value.top(); value.pop(); second_top = value.top(); value.pop(); switch (*it) { 
     case'+':value.push(second_top + top); break; case'-':value.push(second_top - top); break; case'*':value.push(second_top*top); break; case'/':value.push(second_top / top); break; } } } // 输出后缀表达式及其值 cout << prefix << '=' << value.top() << endl; return 0; } bool isoperator(int _C) { 
     return '+' == _C || '-' == _C || '*' == _C || '/' == _C ? true : false; } bool isbrackets(int _C) { 
     return '(' == _C || ')' == _C ? true : false; } 

优化代码： // 后缀表达式求值 #include<iostream> using std::cin; using std::cout; using std::endl; #include<string> using std::string; #include<stack> using std::stack; bool isop(char _C); void orgnize(string&str); int main() { 
     string input, buffer; while (!cin.eof()) { 
     cin >> buffer; input.append(buffer); input.push_back(32); buffer.clear(); } orgnize(input); stack<int>value; for (auto it = input.begin(); it != input.end();) { 
     if (isdigit(*it)) { 
     while (isdigit(*it)) buffer.push_back(*it++); value.push(atoi(buffer.c_str())); buffer.clear(); } else if (isop(*it)) { 
     int top, second_top; top = value.top(); value.pop(); second_top = value.top(); value.pop(); switch (*it++) { 
     case'+':value.push(second_top + top); break; case'-':value.push(second_top - top); break; case'*':value.push(second_top * top); break; case'/':value.push(second_top / top); break; } } else it++; } cout << "postfix(" << input << ")=" << value.top() << endl; return 0; } bool isop(char _C) { 
     return '+' == _C || '-' == _C || '*' == _C || '/' == _C ? true : false; } void orgnize(string&str) { 
     while (!str.empty()) if (isspace(*str.rbegin()))str.pop_back(); else break; while (!str.empty()) if (isspace(*str.begin()))str.erase(str.begin()); else break; for (auto it = str.begin(); it != str.end();) if (isspace(*it++)) while (isspace(*it))it = str.erase(it); for (auto it = str.begin(); it != str.end() - 1; it++) { 
     if (isdigit(*it) && isop(it[1])) it = str.insert(it + 1, 32); else if (isop(*it) && (isdigit(it[1]) || isop(it[1]))) it = str.insert(it + 1, 32); } } 

// 中缀 - 后缀转换 // infix to postfix #include<iostream> using std::cin; using std::cout; using std::ostream; using std::endl; #include<string> using std::string; #include<stack> using std::stack; #include<vector> using std::vector; struct CharInt { 
     bool ischar; int charint; CharInt(bool isch, int chint) :ischar(isch), charint(chint) { 
    } }; ostream&operator<<(ostream&output, CharInt x) { 
     if (x.ischar)output << static_cast<char>(x.charint); else output << x.charint; return output; } bool isop(char _C) { 
     return '+' == _C || '-' == _C || '*' == _C || '/' == _C ? true : false; } int main() { 
     char buffer[128]; cin.getline(buffer, sizeof(buffer)); stack<char>S1; stack<CharInt>S2; for (auto it = buffer; *it;) { 
     if (isdigit(*it)) { 
     string temp; while (isdigit(*it)) temp.push_back(*it++); S2.push(CharInt(false, atoi(temp.c_str()))); } else if (isop(*it)) { 
     CASE_ISOP: if (S1.empty() || '(' == S1.top())S1.push(*it); else if (('+' == S1.top() || '-' == S1.top()) && ('*' == *it || '/' == *it)) S1.push(*it); else { 
     S2.push(CharInt(true, S1.top())); S1.pop(); goto CASE_ISOP; } it++; } else if ('(' == *it)S1.push(*it++); else if (')' == *it++) { 
     while (S1.top() != '(') { 
     S2.push(CharInt(true, S1.top())); S1.pop(); } S1.pop(); } } while (!S1.empty()) { 
     S2.push(CharInt(true, S1.top())); S1.pop(); } vector<CharInt>output; while (!S2.empty()) { 
     output.insert(output.begin(), S2.top()); S2.pop(); } for (auto it : output) cout << it << ' '; cout.put(10); return 0; }