精华内容
下载资源
问答
  • 中缀表达式

    2019-09-24 12:27:49
    3:中缀表达式的值 总时间限制:200ms内存限制:1024kB描述人们熟悉的四则运算表达式称为中缀表达式,例如(23+34*45/(5+6+7))。在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆...

    3:中缀表达式的值

    总时间限制: 
    200ms
    内存限制: 
    1024kB
    描述
    人们熟悉的四则运算表达式称为中缀表达式,例如(23+34*45/(5+6+7))。在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆波兰表示法),并最终变为计算机可以直接执行的指令,得到表达式的值。

    给定一个中缀表达式,编写程序,利用堆栈的方法,计算表达式的值。
    输入
    第一行为测试数据的组数N
    接下来的N行,每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号,操作数都是正整数,数和运算符、括号之间没有空格。中缀表达式的字符串长度不超过600。
    输出
    对每一组测试数据输出一行,为表达式的值
    样例输入
    3
    3+5*8
    (3+5)*8
    (23+34*45/(5+6+7))
    
    样例输出
    43
    64
    108
    
    提示
    注意:运算过程均为整数运算(除法运算'/'即按照C++定义的int除以int的结果,测试数据不会出现除数为0的情况),输出结果也为整数(可能为负)。
    中间计算结果可能为负。

     

    #include<iostream>
    #include<cstring>
    using namespace std;
    char exp[650];
    char op[650];
    int num[650];
    int eptr, optr, nptr;
    void process(char op) {
    int num2 = num[nptr --];
    int num1 = num[nptr];
    int res;
    switch(op) {
    case '+':res = num1 + num2; break;
    case '-':res = num1 - num2; break;
    case '*':res = num1 * num2; break;
    case '/':res = num1 / num2; break;
    default:res = 0;
    }
    num[nptr] = res;
    }
    int main() {
    int N; cin >> N;
    while (N --) {
    scanf("%s", exp);
    eptr = optr = 0;
    nptr = -1;
    op[optr] = '(';
    int length = strlen(exp);
    exp[length] = ')';
    exp[length + 1] = '\0';
    while (exp[eptr] != '\0') {
    if (exp[eptr] >= '0' && exp[eptr] <= '9') {
    int cnum = atoi(exp + eptr);
    num[++ nptr] = cnum;
    while (eptr <= length && exp[eptr] >= '0' && exp[eptr] <= '9') eptr ++;
    }
    else {
    switch (exp[eptr]) {
    case '(': {
    op[++ optr] = '(';
    break;
    }
    case ')': {
    while (op[optr] != '(') {
    process(op[optr]);
    optr --;
    }
    optr --;
    break;
    }
    case '-':;
    case '+': {
    if (op[optr] != '(') {
    process(op[optr]);
    optr --;
    eptr --;//为了循环,将所有运算级别比'+'小的都算了。注意左边的'+''—'一定大于右边的
    }
    else
    op[++ optr] = exp[eptr];
    break;
    }
    case '/':;
    case '*': {
    if (op[optr] == '*' || op[optr] == '/') {
    process(op[optr]);
    optr --;
    eptr --;
    }
    else
    op[++ optr] = exp[eptr];
    break;
    }
    default:break;
    }
    eptr ++;
    }
    }
    cout << num[0] << endl;
    }
    }

    转载于:https://www.cnblogs.com/StillLife/p/7554956.html

    展开全文
  • 中缀表达式转后缀表达式

    万次阅读 多人点赞 2019-04-12 17:55:21
    因为中缀表达式便于人们的理解与计算,但是后缀表达式更方便计算机的运算(如二叉树、堆栈的方法计算),因此在读取一个中缀表达式后,我们得办法将他转化为后缀表达式。 转化方式有三种: 首先假设我们需要转化.....

    自从找完工作人就废了,幡然醒悟不行不行,得把忘记的都记下来。。。。。。

    中缀表达式就是我们正常使用的那种,例如:a+b*c

    后缀表达式就是abc*+;

    为什么要有中缀表达式和后缀表达式呢?

    因为中缀表达式便于人们的理解与计算,但是后缀表达式更方便计算机的运算(如二叉树、堆栈的方法计算),因此在读取一个中缀表达式后,我们得办法将他转化为后缀表达式。

    转化方式有三种:

    首先假设我们需要转化的中缀表达式为:

    a + b * c + ( d * e + f ) * g

    第一种:基于堆栈的算法

    1. 从左到右扫描每一个字符。如果扫描到的字符是操作数(如a、b等),就直接输出这些操作数。

      c++堆栈的应用:中缀表达式转化为后缀表达式

    2. 如果扫描到的字符是一个操作符,分三种情况:

      (1)如果堆栈是空的,直接将操作符存储到堆栈中(push it)

      (2)如果该操作符的优先级大于堆栈出口的操作符,就直接将操作符存储到堆栈中(push it)

      (3)如果该操作符的优先级低于堆栈出口的操作符,就将堆栈出口的操作符导出(pop it), 直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中(push)。

      c++堆栈的应用:中缀表达式转化为后缀表达式

      c++堆栈的应用:中缀表达式转化为后缀表达式

    3. 如果遇到的操作符是左括号"(”,就直接将该操作符输出到堆栈当中。该操作符只有在遇到右括号“)”的时候移除。这是一个特殊符号该特殊处理。

      c++堆栈的应用:中缀表达式转化为后缀表达式

      c++堆栈的应用:中缀表达式转化为后缀表达式

      c++堆栈的应用:中缀表达式转化为后缀表达式

    4. 如果扫描到的操作符是右括号“)”,将堆栈中的操作符导出(pop)到output中输出,直到遇见左括号“(”。将堆栈中的左括号移出堆栈(pop )。继续扫描下一个字符

      c++堆栈的应用:中缀表达式转化为后缀表达式

    5. 如果输入的中缀表达式已经扫描完了,但是堆栈中仍然存在操作符的时候,我们应该讲堆栈中的操作符导出并输入到output 当中。

      c++堆栈的应用:中缀表达式转化为后缀表达式

      c++堆栈的应用:中缀表达式转化为后缀表达式

    第二种:括号法,这种真的很简单啊,好记又简单

          1:按照运算符的优先级对所有的运算单位加括号~

          式子变成拉:((a+(b*c))+(((d*e+f)*g))

           2:转换前缀与后缀表达式

          前缀:把运算符号移动到对应的括号前面

          则变成拉:+(+(a*(bc))*(+(*(de)+g))

          把括号去掉:++a*bc*+*de+g 前缀式子出现

          后缀:把运算符号移动到对应的括号后面

          则变成拉:((a(bc)*)+(((de)*f)+g)*)+

          把括号去掉:abc*+de*f+g *+后缀式子出现

    第三种:利用语法树

          1、将式子转化为二叉树,如下所示,图做的有点丑,懒得画了,不要介意。。。。。。

          2、通过后序遍历将其写出来,即可得到结果:abc*+de*f+g *+

    在这里补充一点,如何将表达式变成二叉树:

    表达式生成树的特点为:

        a. 叶子节点都是操作数;

        b. 非叶子节点都是运算符;

        c. 树根的运算符优先级低;

    步骤如下

    找到表达式中优先级最低的运算符作为树根(注意括号会提升内部的优先级),并将原表达式分解成左右两个表达式;

    分别对左右表达式做步骤1, 左边生成的树为树根的左子树,右边生成的树为树根的右子树;

    重复步骤1,2, 直到分解的表达式里没有运算符(只剩下数字)为止;

    注意一点:在遇到像本式中a后面的+号和c后面的+的优先级问题,在正常计算时a后面的+会先使用所以他的优先级比c后面的+优先级高。所以能得到上面的二叉树。

    后序遍历的问题看我其他的文章中有介绍。

     

     

     

    展开全文
  • 中缀表达式就是我们正常工作中写的表达式,如 a+(b-c)*d ,编译系统将中缀表达式改写 abc-d*+ ,这种运算符在操作数后面称为后缀表达式(也称逆波兰表达式)。如何实现转换的呢?这里做一下自己的理解及记录。利用栈来...

    中缀表达式就是我们正常工作中写的表达式,如 a+(b-c)*d ,编译系统将中缀表达式改写 abc-d*+ ,这种运算符在操作数后面称为后缀表达式(也称逆波兰表达式)。

    如何实现转换的呢?这里做一下自己的理解及记录。

    利用栈来实现

    转换过程需要用到栈,这里用两个栈,stack 栈用来存放运算符,post 栈用来存放最后的后缀表达式。具体规则如下:

    从左到右扫描中缀表达式,若是操作数,直接存入 post 栈;

    若是运算符:

    (1)该运算符是左括号 ( , 则直接存入 stack 栈。

    (2)该运算符是右括号 ),则将 stack 栈中 ( 前的所有运算符出栈,存入 post 栈。

    (3)若该运算符为非括号,则将该运算符和 stack 栈顶运算符作比较:若高于栈顶运算符,则直接存入 stack 栈,否则将栈顶运算符出栈(从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止),存入 post 栈。

    (4)当扫描完后,stack 栈中还有运算符时,则将所有运算符出栈,存入 post 栈。

    例子:中缀表达式 a + b * c + (d * e + f) * g,其转换成后缀表达式则为a b c * + d e * f + g * +。

    扫描

    stack 栈

    post 栈

    a

    a

    a+

    +

    a

    a+b

    +

    ab

    a+b*

    +*

    ab

    a+b*c

    +*

    abc

    a+b*c+

    +

    abc*+

    a+b*c+(

    +(

    abc*+

    a+b*c+(d

    +(

    abc*+d

    a+b*c+(d*

    +(*

    abc*+d

    a+b*c+(d*e

    +(*

    abc*+de

    a+b*c+(d*e+

    +(+

    abc*+de*

    a+b*c+(d*e+f

    +(+

    abc*+de*f

    a+b*c+(d*e+f)

    +

    abc*+de*f+

    a+b*c+(d*e+f)*

    +*

    abc*+de*f+

    a+b*c+(d*e+f)*g

    +*

    abc*+de*f+g

    a+b*c+(d*e+f)*g#

    abc*+de*f+g*+

    注意:表格中第6步,读到+,因为栈顶元素*的优先级高,所以*出栈,栈中下一个元素+优先级与读到的操作符+一样,所以也要弹出。然后再将读到的+压入栈中。

    第13步,读到),则直接将栈中元素弹出直到遇到(为止。这里左括号前只有一个操作符+被弹出。

    代码实现

    import java.util.Stack;

    public class InToPost {

    private Stack opStack;

    private Stack outStack;

    private String input;

    public InToPost(String in) {

    input = in;

    opStack = new Stack();

    outStack = new Stack();

    }

    public Stack doTrans() { //其他类型自行转换

    for (int i = 0; i < input.length(); i++) {

    char ch = input.charAt(i);

    switch (ch) {

    case '+':

    case '-':

    operationOpStack(ch, 1);

    break;

    case '*':

    case '/':

    operationOpStack(ch, 2);

    break;

    case '(':

    opStack.push(ch);

    break;

    case ')':

    operationParen();

    break;

    default:

    outStack.push(ch);

    break;

    }

    }

    while (!opStack.isEmpty()) {

    outStack.push(opStack.pop());

    }

    return outStack;

    }

    public void operationOpStack(char opThis, int prec1) {//运算符栈操作

    while (!opStack.isEmpty()) {

    char opTop = opStack.pop();

    if (opTop == '(') {

    opStack.push(opTop);

    }

    else {

    int prec2;

    if (opTop == '+' || opTop == '-')

    prec2 = 1;

    else

    prec2 = 2;

    if (prec2 < prec1) {

    opStack.push(opTop);

    break;

    }

    else

    outStack.push(opTop);

    }

    }

    opStack.push(opThis);

    }

    public void operationParen() {

    while (!opStack.isEmpty()) {

    char c = opStack.pop();

    if (c == '(')

    break;

    else

    outStack.push(c);

    }

    }

    public static void main(String[] args) {

    String input = "1+2*4/5-7+3/6";

    InToPost theTrans = new InToPost(input);

    Stack output = theTrans.doTrans();

    System.out.println("Postfix is " + output + '\n');

    }

    }

    利用语法树

    先将中缀表达式用二叉树表示出来,再后序遍历该二叉树,就得到其相应的后缀表达式。

    加括号法

    加括号法先将中缀表达式每步要计算的表达式加上括号,然后将每个运算符移到其所在括号的外面,最后,从左到右去掉括号后就是后缀表达式。

    例子: a+(b-c)*d

    加括号 (a+((b-c)d))

    移运算符 (a((bc)-d))+

    去括号 abc-d*+

    后缀表达式求值

    求值过程可用栈来辅助存储。假定待求值的后缀表达式为:6 5 2 3 + 8 * + 3 + *,则其求值过程如下:

    遍历表达式,遇到数字首先放入栈,此时栈如下 6 5 2 3

    接着读到+,则弹出3和2,执行3+2,将结果5压栈 6 5 5

    读到8,压栈 6 5 5 8

    读到 *, 弹出8和5,执行8*5,将结果40压栈 6 5 40

    读到 +,弹出40和5,执行40+5,将结果45压栈 6 45

    读到 3,压栈 6 45 3

    读到 +,弹出3和45,执行3+45,将结果48压栈 6 48

    读到 *,弹出48和6,执行48*6,将结果288压栈 288

    最后结果288

    展开全文
  • 我们把平时所用的标准四则运算表达式,即“9+(3-1)*3+10/2"叫做中缀表达式。因为所有的运算符号都在两数字的中间,现在我们的问题就是中缀到后缀的转化。中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“9 3 1-3*+ ...

    我们把平时所用的标准四则运算表达式,即“9+(3-1)*3+10/2"叫做中缀表达式。因为所有的运算符号都在两数字的中间,现在我们的问题就是中缀到后缀的转化。

    中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“9 3 1-3*+ 10 2/+”

    规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于找顶符号(乘除优先加减)则栈顶元素依次出找并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。

    下面我们来具体看看这个过程。

    1. 初始化一空栈,用来对符号进出栈使用。

    2. 第一个字符是数字9,输出9,后面是符号“+”,进栈。

    7b963aa914de3f76be2ae87e7a61e56d.png

    3. 第三个字符是“(”,依然是符号,因其只是左括号,还未配对,故进栈。

    4. 第四个字符是数字3,输出,总表达式为9 3,接着是“-”进栈。

    c53c4071937a3b8f774611b0ab57a9c5.png

    5. 接下来是数字1,输出,总表达式为9 3 1,后面是符号“)”,此时,我们需要去匹配此前的“(”,所以栈顶依次出栈,并输出,直到“(”出栈为止。此时左括号上方只有“-”,因此输出“-”,总的输出表达式为9 3 1 -

    6. 接着是数字3,输出,总的表达式为9 3 1 - 3 。紧接着是符号“*”,因为此时的栈顶符号为“+”号,优先级低于“*”,因此不输出,进栈。

    eea1fb3a834e7fe9c54b862ff7c7792a.png

    7. 之后是符号“+”,此时当前栈顶元素比这个“+”的优先级高,因此栈中元素出栈并输出(没有比“+”号更低的优先级,所以全部出栈),总输出表达式为 9 3 1 - 3 * +.然后将当前这个符号“+”进栈。也就是说,前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”,而下图中的栈底(也是栈顶)的“+”是指“9+(3-1)*3+”中的最后一个“+”。

    8. 紧接着数字10,输出,总表达式变为9 3 1-3 * + 10。

    e8e8570d8c871f79df5c90ec57b12298.png

    9. 最后一个数字2,输出,总的表达式为 9 3 1-3*+ 10 2

    10. 因已经到最后,所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1-3*+ 10 2/+

    388939828635f695fa72ef1b9a68a40d.png

    从刚才的推导中你会发现,要想让计算机具有处理我们通常的标准(中缀)表达式的能力,最重要的就是两步:

    将中缀表达式转化为后缀表达式(栈用来进出运算的符号)。

    将后缀表达式进行运算得出结果(栈用来进出运算的数字)。

    整个过程,都充分利用了找的后进先出特性来处理,理解好它其实也就理解好了栈这个数据结构。

    延伸阅读

    此文章所在专题列表如下:

    展开全文
  • Infix expression invert to Reverse Polish expression前缀表达式(Polish expression, 波兰表达式)中缀表达式(Infix expression)后缀表达式(Reverse Polish expression, 逆波兰表达式)中缀表达式(Infix expression...
  • 首先需要将中缀表达式转化为后缀表达式 然后通过后缀表达式求值 第一步(中缀表达式-&gt;后缀表达式)的思路: 定义一个操作符栈stack&lt;char&gt; s,一个队列queue&lt;string&gt;q用来存放...
  • 中缀表达式转后缀表达式中缀表达式转后缀表达式的规则。1.遇到操作数:直接输入到后缀表达式栈2.遇到运算符,直接入操作符栈3.遇到左括号:直接将其入栈4.遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈...
  • 给你一个中缀表达式,就是平常的算术式,比如这样的1+4/2*3+4 求计算结果 没有提交,我编几个样例把。 【输入样例】: (((1))) (((1+1))) 1+4/2*3+4 1+4/(2*3)+4 1+120/(20*3)+1 【输出样例】: 1 2 11 5 4 ...
  • 大家看到,后缀表达式适合计算式进行运算,但是人却不太容易写出来,尤其是表达式很长的情况下,因此在开发中,我们需要将 中缀表达式转成后缀表达式。具体步骤如下:1.初始化两个栈:运算符栈s1和储存中间结果的栈s2...
  • 大家看到,后缀表达式适合计算式进行运算,但是人却不太容易写出来,尤其是表达式很长的情况下,因此在开发中,我们需要将 中缀表达式转成后缀表达式。具体步骤如下:1.初始化两个栈:运算符栈s1和储存中间结果的栈s2...
  • 中缀表达式 后缀表达式by Pramod Sripada 通过Pramod Sripada 中缀表达式VS后缀表达式,以及如何构建更好JavaScript计算器 (Infix Expressions VS Postfix Expressions, and How to Build a Better JavaScript ...
  • /*中缀表达式转成后缀表达式 "12+((22+31)*4)-5" ==> 12 22 31 + 4 * + 5 -第一步,将中缀表达式转成中缀字符串list,方便遍历 [12, +, (, (, 22, +, 31, ), *, 4, ), -, 5]第二步,将中缀字符串list转成后缀...
  • /*中缀表达式转成后缀表达式 "12+((22+31)*4)-5" ==> 12 22 31 + 4 * + 5 -第一步,将中缀表达式转成中缀字符串list,方便遍历 [12, +, (, (, 22, +, 31, ), *, 4, ), -, 5]第二步,将中缀字符串list转成后缀...
  • 中缀表达式转换为后缀表达式(Java) 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢! 步骤 初始化两个栈:运算符栈 s1 和储存中间结果的...
  • 将简单的中缀表达式转换成表达式树,然后利用表达式树对中缀表达式进行求值。
  • 中缀表达式,即运算符在操作数中间。 计算中缀表达式时,逐个扫描表达式。 扫描时存入两个栈,操作数栈,和运算符栈。 例如 3*2^(4+2*2-1*3)-5  扫描表达式。 操作数栈以 栈$表示,运算符栈以 栈¥表示。 扫描...
  • 3、从右至左扫描中缀表达式,如果是数字,就直接压入结果栈 若是运算符,则与运算符栈顶元素比较优先级:若该运算符优先级大于等于栈顶元素,则将该运算符入栈 否则栈内元素出栈并压入结果栈,再与其比较,直到该...
  • 中缀表达式-------->前缀表达式 方法一:将操作操作的两个对象放在操作符的后边便可将中缀表达式构成前缀表达式,(将优先级高的操作符和操作数先结合,然后加上括号,最后输出的时候 ,把括号去了即可) 例1:a+b...
  • 在Java编程中,如何将中缀表达式转换为后缀表达式?以下示例演示如何使用堆栈的概念将中缀转换为后缀表达式。package com.yiibai; import java.io.IOException; public class Infix2Postfix { private Stack the...
  • 中缀表达式:通用的算术或逻辑公式表示方法,操作符是以中缀的形式处于操作数的中间,平时常用的算术表示方法。 后缀表达式: 后缀表达式是将操作符置于操作数的后面,如:3 4 +;后缀表达式的表达方式不唯一,如...
  • 本文主要内容:表达式的三种形式中缀表达式与后缀表达式转换算法一、表达式的三种形式:中缀表达式:运算符放在两个运算对象中间,如:(2+1)*3。我们从小做数学题时,一直使用的就是中缀表达式。后缀表达式:不包含...
  • 1.人脑计算(中缀表达式)我们计算一个式子是从左往右看,遇到数先保留在脑子里,遇到运算符也先存在大脑,接着遇到下一个数,还得看看这个数后面有没有更高等级的运算符,遇到左括号得把之前的东西都先放着,再往后...
  • 先把中缀表达式转为后缀表达式,再入栈计算。转化主要遵循以下原则:1.遇到操作数,直接输出;2.栈为空时,遇到运算符,入栈;3.遇到左括号,将其入栈;4.遇到右括号,执行出栈操作,并将出栈的元素输出,直到弹出栈...
  • 中缀表达式转后缀表达式的方法

    万次阅读 多人点赞 2020-08-03 22:13:54
    表达式求值: 1.从左到右进行遍历 2.运算数,直接输出. 3.左括号,直接压入堆栈,(括号是最高优先级,无需比较)(入栈后优先级降到最低,确保其他符号正常入栈) 4.右括号,(意味着括号已结束)不断弹出栈顶运算符并输出直到...
  • /*将中缀表达式转换为后缀表达式定义优先级:'(':4'*', '/' :3'+', '-':2')':1思路:循环遍历输入字符数组if input[i]是数字,则print; continue;循环if栈空,则input[i]入栈,break;if outputPriority < ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,558
精华内容 3,823
关键字:

中缀表达式