逆波兰表达式

• 可参照文章逆波兰表达式

算法分析

• 若当前字符是操作数，则压栈
• 若当前字符是操作符，则弹出栈中的两个操作数，计算后仍然压入栈中

C++代码实现

/* 后缀表达式（逆波兰表达式） 有效操作只有'+'、'-'、'*'、'/'，且操作数是整数 */ #include<iostream> #include<string> #include<assert.h> #include<cstring>  using namespace std;  #define OVERFLOW -2 #define OK 1 #define ERROR -1  typedef int Status; typedef int SElemType;  typedef struct StackNode {     SElemType data;     struct StackNode* next; }StackNode, * LinkStack;  // 链栈初始化 void InitStack(LinkStack& S) {     S = NULL; }  // 判断链栈是否为空 Status StackEmpty(LinkStack S) {     if (S == NULL) return 1;     else return 0; }  // 得到栈顶元素 Status GetTop(LinkStack S, SElemType& e) {     if (StackEmpty(S)) return ERROR;     e = S->data;     return OK; }  // 判断栈中是否只有一个元素 bool IsOne(LinkStack S) {     if (StackEmpty(S)) return false;     LinkStack p;     p = S;     int i = 0;     while (p) {         i++;         p = p->next;     }     if (i == 1) return true;     else return false; }  // 入栈 Status Push(LinkStack& S, SElemType e) {     LinkStack p;     p = new StackNode;     if (!p) exit(OVERFLOW);     p->data = e;     p->next = S;     S = p;     return OK; }  // 出栈 Status Pop(LinkStack& S, SElemType& e) {     if (StackEmpty(S)) return ERROR;     LinkStack p;     e = S->data;     p = S;     S = S->next;     delete p;     p = NULL;     return OK; }  // 判断是否为数字 bool IsNum(char ch) {     if (ch > '0' && ch < '9')         return true;     return false; }  Status f(const char* str, SElemType& e) { //    const char* str = str.c_str();     assert(str);  // 断言 参数     int size = strlen(str);     int i = 0;     LinkStack S;     InitStack(S);     int temp = 0;     for (; i < size; i++) {         if (IsNum(str[i]))             // 转换为数字             temp = temp * 10 + str[i] - '0';          else if (str[i] == ' ') {             if (IsNum(str[i - 1])) {                 // 当前字符为空格，且前一个为数字，入栈                 Push(S, temp);                 temp = 0;             }         }         else {             if (IsOne(S)) {                 // 栈中只有一个元素                 cout << "表达式有误，无法计算！" << endl;                 return ERROR;             }             Pop(S, e);             int a = e;  // 右操作数             Pop(S, e);             int b = e;  // 左操作数             switch (str[i]) {             case '+':                 Push(S, b + a);                 break;             case '-':                 Push(S, b - a);                 break;             case '*':                 Push(S, b * a);                 break;             case '/':                 if (a == 0) {                     cout << "被除数为零，无法计算！" << endl;                     return ERROR;                 }                 else {                     Push(S, b / a);                     break;                 }             }         }      }     if (!IsOne(S)) {         cout << "表达式操作数过多！" << endl;         return ERROR;     }     else {         Pop(S, e);         e = e;         return OK;     }  }  int main() {     SElemType e;     const char* str = "1 3 + 4 * 4 /";     f(str, e);     cout << "结果为: " << e;     return 0; }

结果为: 4

你还在原价购买阿里云、腾讯云、华为云、天翼云产品？那就亏大啦！现在申请成为四大品牌云厂商VIP用户，可以3折优惠价购买云服务器等云产品，并且可享四大云服务商产品终身VIP优惠价，还等什么？赶紧点击下面对应链接免费申请VIP客户吧：

1、点击这里立即申请成为腾讯云VIP客户

2、点击这里立即注册成为天翼云VIP客户

3、点击这里立即申请成为华为云VIP客户

4、点击这里立享阿里云产品终身VIP优惠价

喜欢 (0)赏

[[email protected]]

分享 (0)