C++ 堆栈转后缀表达式

C++ 堆栈转后缀表达式 首页 / C++入门教程 / C++ 堆栈转后缀表达式

中缀表达式

前缀表达式是在两个操作数之间写入运算符(+,-,*,/)的表达式。例如,考虑以下表达式:

A + B
A + B - C
(A + B) + (C - D)

在这里,我们在操作数A和B之间编写了'+'运算符,并在C和D操作数之间编写了-运算符。

后缀表达式

后缀运算符还包含运算符和操作数。在后缀表达式中,运算符写在操作数之后。也称为反向波兰符号。例如,考虑以下表达式:

A B +   
A B + C -   
A B C * +
A B + C * D -

中缀转后缀表达式算法

以下是算法,用于将中缀表达式转换为反向波兰语表示法。

  1. 初始化堆栈。
  2. 在中缀表达式中从左到右扫描运算符。
  3. 如果最左边的字符是操作数,请将其设置为Postfix字符串的当前输出。
  4. 如果扫描的字符是运算符,并且堆栈为空或包含'(',')'符号,则将运算符推入堆栈。
  5. 如果扫描的运算符的优先级高于堆栈中现有的优先级运算符,或者如果堆栈为空,则将其放在堆栈中。
  6. 如果扫描的运算符的优先级低于堆栈中现有的运算符,请弹出所有堆栈运算符。之后,将扫描的运算符推入堆栈。
  7. 如果扫描的字符是左括号'(',则将其推入堆栈。
  8. 如果遇到右括号')',请弹出堆栈并打印所有输出字符串,直到遇到'('并丢弃两个括号。
  9. 重复从2到8的所有步骤,直到infix表达式为扫描。
  10. 打印堆栈输出。
  11. 从堆栈中弹出并输出所有字符,包括运算符,直到不为空为止。

让我们将一个中缀表达式转换为堆栈中的后缀表达式:

链接:https://www.learnfk.comhttps://www.learnfk.com/c++/program-to-convert-infix-to-postfix-expression-in-cpp-using-the-stack-data-structure.html

来源:LearnFk无涯教程网

在这里,我们有中缀表达式((A *(B + D)/ E)-F *(G + H/K)))转换为其等效的后缀表达式:

标签号已扫描符号堆栈表达式
1((
2(((
3 A(( A
4 *((* * ) A
5(((*()) A
6 B((*()) AB
7 +(((*(+ ))) AB
8 D(((*(+ ))) ABD
9)((* * ) ABD +
10/((* * ) ABD +
11 E((* * ) ABD + E
12)( ABD + E/*
13-(- ABD + E/*
14((-( ABD + E/*
15 F(-( ABD + E/* F
16 *(-(* ) ABD + E/* F
17((-(*()) ABD + E/* F
18 G(-(*()) ABD + E/* FG
19 +(-(*(+ )) ABD + E/* FG
20 H(-(*(+ )) ABD + E/* FGH
21/(-(*(+/)) ABD + E/* FGH
22 K(-(*(+/)) ABD + E/* FGHK
23)(-(* ) ABD + E/* FGHK/+
24)(- ABD + E/* FGHK/+ *
25) ABD + E/* FGHK/+ *-

程序将中缀表达式转换为后缀表达式

让我们创建一个C++程序,将中缀表达式转换为后缀表达式

#include<iostream>
#include<stack>
using namespace std;
// 定义运算符、操作数、equalOrhigher 优先级的布尔函数和字符串转换函数。
bool IsOperator(char);
bool IsOperand(char);
bool eqlOrhigher(char, char);
string convert(string);

int main()
{
  string infix_expression, postfix_expression;
  int ch;
  do
  {
      cout << " Enter an infix expression: ";
      cin >> infix_expression;
      postfix_expression = convert(infix_expression);
      cout << "\n Your 中缀表达式 is: " << infix_expression;
      cout << "\n Postfix expression is: " << postfix_expression;
      cout << "\n \t Do you want to enter infix expression (1/ 0)?";
      cin >> ch;
      //cin.ignore(); 
  } while(ch == 1);
  return 0;
}

// 定义 IsOperator() 函数来验证是否有任何符号是运算符。
/* 如果符号是运算符,则返回 true,否则返回 false。 */
bool IsOperator(char c)
{
  if(c == '+' || c == '-' || c == '*' || c == '/' || c == '^' )
     return true;   
  return false;
}

// IsOperand() 函数用于验证字符是否为操作数。
bool IsOperand(char c)
{
  if( c >= 'A' && c <= 'Z')  /* 定义 A 到 Z 之间的字符。如果不是,则返回 False。*/
    return true;
  if (c >= 'a' && c <= 'z') //定义 a 到 z 之间的字符。如果不是,则返回 False。 */
    return true;
  if(c >= '0' && c <= '9')  //将字符定义在 0 到 9 之间。如果不是,则返回 False。 */
    return true;
  return false;
}
// 在这里,precedence() 函数用于定义运算符的优先级。
int precedence(char op)
{
  if(op == '+' || op == '-')                   /* 它定义了最低优先级 */
    return 1;
  if (op == '*' || op == '/')
    return 2;
  if(op == '^')                                  /* 指数运算符具有最高优先级 */
    return 3;      
  return 0;
}
/* eqlOrhigher() 函数用于检查中缀表达式中两个运算符的更高或相等优先级。 */
bool eqlOrhigher (char op1, char op2)
{
  int p1 = precedence(op1);
  int p2 = precedence(op2);
  if (p1 == p2)
  {
    if (op1 == '^' )
      return false;
    return true;
  }
  return  (p1>p2 ? true : false);
}

/* string convert() 函数用于将中缀表达式转换为 Stack 的后缀表达式 */
string convert(string infix)
{
  stack <char> S;
  string postfix ="";  
  char ch;

  S.push( '(' );
  infix += ')';

  for(int i = 0; i<infix.length(); i++)
  {
    ch = infix[i];
    if(ch == ' ')
      continue;
    else if(ch == '(')
      S.push(ch);
    else if(IsOperand(ch))
      postfix += ch;
    else if(IsOperator(ch)){
      while(!S.empty() && eqlOrhigher(S.top(), ch)){
        postfix += S.top();
        S.pop();
      }
      S.push(ch);
    }else if(ch == ')'){
      while(!S.empty() && S.top() != '('){
         postfix += S.top();
         S.pop();
      }
      S.pop();
    }
  }
  return postfix;
}

输出:

Program to convert infix to postfix expression in C++ using the Stack Data Structure

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

AI技术内参 -〔洪亮劼〕

从0开始学微服务 -〔胡忠想〕

代码精进之路 -〔范学雷〕

苏杰的产品创新课 -〔苏杰〕

移动端自动化测试实战 -〔思寒〕

用户体验设计实战课 -〔相辉〕

操作系统实战45讲 -〔彭东〕

超级访谈:对话汤峥嵘 -〔汤峥嵘〕

深入浅出可观测性 -〔翁一磊〕

好记忆不如烂笔头。留下您的足迹吧 :)