使用C++栈实现表达式运算 |21xrx.com

使用C++栈实现表达式运算

2023-07-03 22:04:05 深夜i 10 0

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++栈实现表达式运算，提高程序设计效率，降低程序设计难度。

上一篇: idea打包java可执行jar包

下一篇: C++ 数组存储数据的实现方法

评论区

相似文章