21xrx.com
2024-11-22 10:01:08 Friday
登录
文章检索 我的文章 写文章
使用C++栈实现表达式运算
2023-07-03 22:04:05 深夜i     --     --
C++ 表达式 运算 实现

在程序设计中,表达式运算是一项非常常见的操作。在C++中,可以使用栈来实现表达式运算,这样可以更加简洁易懂地编写代码。

首先,在使用栈实现表达式运算的时候,我们需要定义一个栈结构体。该结构体包含了一个数组和一个栈顶标志位。栈顶标志位用来记录当前栈中最新元素所在数组的下标,这样我们就可以知道下一个元素应该插入哪个位置了。

代码示例:


struct Stack {

  int array[1000];

  int top = -1;

};

接下来,我们需要定义一些基本的栈操作,例如入栈和出栈。在入栈操作中,我们需要将元素插入到数组最后一个空闲位置,并将栈顶标志位增加1。而在出栈操作中,我们需要返回最新的元素,并将栈顶标志位减少1。

代码示例:


void push(Stack& st, int x) {

  st.array[++st.top] = x;

}

int pop(Stack& st) {

  return st.array[st.top--];

}

接下来,我们就可以开始实现表达式运算了。表达式的运算可以分为两个步骤:中缀表达式转后缀表达式以及后缀表达式的计算。

对于中缀表达式转后缀表达式,我们可以采用栈来存储运算符。从左往右遍历中缀表达式,遇到数字直接输出,而遇到运算符则需要将其存入栈中。如果遇到左括号,则直接入栈;而如果遇到右括号,则不断出栈并输出,直到遇到左括号为止。我们需要维护一个运算符优先级的顺序,以便判断是否需要将栈中的元素出栈。

代码示例:


int getPriority(char op) {

  if (op == '(') return 0;

  if (op == '+' || op == '-') return 1;

  if (op == '*' || op == '/') return 2;

}

string infixToSuffix(string infix) {

  Stack st;

  string suffix = "";

  for (int i = 0; i < infix.size(); i++) {

    if (isdigit(infix[i])) {

      suffix += infix[i];

      while (i + 1 < infix.size() && isdigit(infix[i + 1])) {

        suffix += infix[++i];

      }

      suffix += " ";

    } else if (infix[i] == '(') {

      push(st, infix[i]);

    } else if (infix[i] == ')') {

      while (st.top >= 0 && st.array[st.top] != '(') {

        suffix += st.array[st.top--];

        suffix += " ";

      }

      st.top--;

    } else {

      while (st.top >= 0 && getPriority(infix[i]) <= getPriority(st.array[st.top])) {

        suffix += st.array[st.top--];

        suffix += " ";

      }

      push(st, infix[i]);

    }

  }

  while (st.top >= 0) {

    suffix += st.array[st.top--];

    suffix += " ";

  }

  return suffix;

}

在得到后缀表达式之后,我们可以采用栈来计算表达式的值。从左往右遍历后缀表达式,如果遇到数字,则将其入栈;如果遇到运算符,则从栈中弹出两个元素进行计算,并将结果压入栈中。最后栈中仅剩一个元素,即为表达式的计算结果。

代码示例:


int evalSuffix(string suffix) {

  Stack st;

  for (int i = 0; i < suffix.size(); i++) {

    if (isdigit(suffix[i])) {

      int num = 0;

      while (i < suffix.size() && isdigit(suffix[i])) {

        num = num * 10 + suffix[i] - '0';

        i++;

      }

      push(st, num);

    } else if (suffix[i] != ' ') {

      int a = pop(st);

      int b = pop(st);

      if (suffix[i] == '+') {

        push(st, b + a);

      } else if (suffix[i] == '-') {

        push(st, b - a);

      } else if (suffix[i] == '*') {

        push(st, b * a);

      } else if (suffix[i] == '/') {

        push(st, b / a);

      }

    }

  }

  return pop(st);

}

最后,我们可以将中缀表达式和后缀表达式的计算结果输出到控制台上,以便进行验证。

代码示例:


int main() {

  string infix = "(1+2)*3-4/2";

  string suffix = infixToSuffix(infix);

  int result = evalSuffix(suffix);

  cout << "Infix: " << infix << endl;

  cout << "Suffix: " << suffix << endl;

  cout << "Result: " << result << endl;

  return 0;

}

通过以上的代码示例,我们可以轻松地使用C++栈实现表达式运算,提高程序设计效率,降低程序设计难度。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复