中缀表达式转后缀表达式逻辑-查看文章

中缀表达式转后缀表达式逻辑

发表于:2023-12-26 15:34:00 分类:开发杂记 阅读:122次

image
  1. 初始化两个栈:运算符栈s1和存中间结果的栈s2;

  2. 从左至右扫描中缀表达式;

  3. 遇到操作数时,将其压s2;

  4. 遇到运算符时,比较其与s1栈顶运算符的优先级:

    1. 如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;

    2. 否则,若优先级比栈顶运算符的高,也将运算符压入s1;

    3. 否则,将s1顶的运算符弹出并压入到s2中,再次转到4.a与s1中新的栈顶运算符相比较;

  5.  遇到括号时:

    1. 如果是左括号“(”,则直接压入s1。

    2. 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃。

  6. 重复步骤2至5,直到表达式的最右边;

  7. 将s1中剩余的运算符依次弹出并压入s2;

  8. 依次弹出2中的元素并输出,结果的逆序即为中级表达式对应的后缀表达式。


关键词:后缀转中缀


验证码: