栈内优先级

栈、队列、优先级队列

2019-06-20 14:29:24

一、栈

栈是临时的数据结构，存储容量很小。遵循后进先出原则（LIFO），栈只允许访问一个数据项：即最后插入的数据项。只有移除这个数据项后才能访问倒数第二个插入的数据项，依此类推。

插入：栈的指针永远指向栈元素，即指向最后插入的元素。当插入数据时，指针会上移一个单元，然后将数据插入至该存储单元。

删除：移除最后插入的栈顶元素，然后指针下移指向新的栈顶元素。栈中被删除的数据还存留在其中，直到被新的数据项覆盖为止，但该项被删除后不能被访问。

查看：只能查看栈顶元素，即最后插入的数据项。

class StackX {
    private int maxSize;
    private long[] stackArray;
    private int top;

    public StackX(int s) {
        maxSize = s;
        stackArray = new long[maxSize];
        top = -1;
    }

    public void push(long j) {
        stackArray[++top] = j
    }

    public long pop() {
        return stackArray[top--];
    }

    public long peek() {
        return stackArray[top];
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isFull() {
        return (top == maxSize - 1);
    }
}

class StackApp {
    public static void main(String[] args) {
        StackX theStack = new StackX(10);
        theStack.push(20);
        theStack.push(40);
        theStack.push(60);
        theStack.push(80);

        while(!theStack.isEmpty()) {
            long value = theStack.pop();
            System.out.println(value);
            System.out.println(" ");
        }
        System.out.println("");
    }
}

实现字符串分隔符匹配栈运用代码示例：

class StackX {
    private int maxSize;
    private long[] stackArray;
    private int top;

    public StackX(int s) {
        maxSize = s;
        stackArray = new long[maxSize];
        top = -1;
    }

    public void push(long j) {
        stackArray[++top] = j
    }

    public long pop() {
        return stackArray[top--];
    }

    public long peek() {
        return stackArray[top];
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isFull() {
        return (top == maxSize - 1);
    }
}

class BracketChecker {
    private String input;
    
    public BracketChecker(String input) {
        this.input = input;
    }

    public void check() {
        int stackSize = input.length();
        StackX theStack = new StackX(stackSize);

        for(int j = 0; j < input.length(); j++) {
            char ch = input.charAt(j);
            switch(ch) {
                case '{':
                case '[':
                case '(':
                    theStack.push(ch);
                    break;
                case '}':
                case ']':
                case ')':
                    if (!theStack.isEmpty()) {
                        char chx = theStack.pop();
                        if ((ch == '}' && chx != '{') ||
                            (ch == ']' && chx != '[') ||
                            (ch == ')' && chx != '('))
                        {
                            System.out.println("Error: " + ch + " at " + j);
                        }
                    } else {
                        System.out.println("Error: " + ch + " at " + j);
                    }
                    break;
                default:
                    break;
            }
        }
        
        if (!theStack.isEmpty()) {
            System.out.println("Error: missing right delimiter");
        }
    }
}      

class BracketsApp {
    public static void main(String[] args) throws IOException {
        String input;
        while(true) {
            System.out.println("Enter string containing delimiters: ");
            System.out.flush();
            input = getString();
            if (input.equals("")) {
                break;
            }

            BracketChecker theChecker = new BracketChecker(input);
            theChecker.check();
        }
    }
                  
    public static String getString() throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;
    }
}

StackX类中实现的栈，数据项入栈和出栈的时间复杂度均为常数O(1)，即栈操作所耗的时间不依赖于栈中数据项的个数，栈不需要比较和移动操作，因此操作时间很短。

二、队列

队列遵循先进先出原则（FIFO），队列和栈一样，插入数据项和移除数据项的时间复杂度均为O(1)。

队列的Java代码：

class Queue {
    private int maxSize;
    private long[] queArray;
    private int front;
    private int rear;
    private int nItems;

    public Queue(int s) {
        maxSize = s;
        queArray = new long[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    public void insert(long j) {
        if (rear == maxSize - 1) {
            rear = -1;
        }
        queArray[++rear] = j;
        nItems++;
    }

    public void remove() {
        long temp = queArray[front++];
        if (front == maxSize) {
            front = 0;
        }
        nItems--;
        return temp;
    }

    public long peekFront() {
        return queArray[front];
    }

    public boolean isEmpty() {
        return (nItems == 0);
    }

    public boolean isFull() {
        return(nItems == maxSize);
    }

    public int size() {
        return nItems;
    }
}

class QueueApp {
    public static void main(String[] args) {
        Queue theQueue = new Queue(5);
        theQueue.insert(10);
        theQueue.insert(20);
        theQueue.insert(30);
        theQueue.insert(40);

        theQueue.remove();
        theQueue.remove();
        theQueue.remove();

        theQueue.insert(50);
        theQueue.insert(60);
        theQueue.insert(70);
        theQueue.insert(80);

        while(!theQueue.isEmpty()) {
            long n = theQueue.remove();
            System.out.print(n);
            System.out.print(" ");
        }
        System.out.println("");
    }
}

class Queue {
    private int maxSize;
    private long[] queArray;
    private int front;
    private int rear;

    public Queue(int s) {
        maxSize = s + 1;
        queArray = new long[maxSize];
        front = 0;
        rear = -1;
    }

    public void insert(long j) {
        if (rear == maxSize - 1) {
            rear = -1;
        }
        queArray[++rear] = j;
    }

    public long remove() {
        long temp = queArray[front++];
        if (front == maxSize) {
            front = 0;
        }
        return temp;
    }

    public long peek() {
        return queArray[front];
    }

    public boolean isEmpty() {
        return (rear + 1 == front || (front + maxSize - 1 == rear));
    }

    public boolean isFull() {
        return(rear + 2 == front || (front + maxSize - 2 == rear);
    }

    public int size() {
        if (rear >= front)
            return rear - front + 1;
        else
            return (maxSize - front) + (rear + 1);
    }
}

class QueueApp {
    public static void main(String[] args) {
        Queue theQueue = new Queue(5);
        theQueue.insert(10);
        theQueue.insert(20);
        theQueue.insert(30);
        theQueue.insert(40);

        theQueue.remove();
        theQueue.remove();
        theQueue.remove();

        theQueue.insert(50);
        theQueue.insert(60);
        theQueue.insert(70);
        theQueue.insert(80);

        while(!theQueue.isEmpty()) {
            long n = theQueue.remove();
            System.out.print(n);
            System.out.print(" ");
        }
        System.out.println("");
    }
}

注：双端队列就是一个两端都是结尾的队列。队列的每一端都可以插入数据和移除数据。

三、优先级队列

更多相关内容

中缀表达式计算中栈内优先级、栈外优先级的排序原理
千次阅读 多人点赞 2019-10-12 10:33:11
有关中缀表达式计算是数据结构中非常经典的题目，以至于很多文章或课本喜欢直接给出计算方法一步到位，但关于其中的原理却并未深究，本文试图通过分析运算符的栈内优先级，栈外优先级的排序方法探求中缀表达式计算...
前言：

有关中缀表达式计算是数据结构中非常经典的题目，以至于很多文章或课本喜欢直接给出计算方法一步到位，但关于其中的原理却并未深究，本文试图通过分析运算符的栈内优先级，栈外优先级的排序方法探求中缀表达式计算中的原理。为了简便起见，在本文的讨论中只考虑双目运算符（仅＋、－、＊、/ 　四种）以及括号。并默认输入的表达式正确。

引用：

请看完这篇文章以对中缀表达式的计算有一个大体的了解：

《中缀和后缀算术表达式的分析比较》刘爱贵（高能物理研究所计算中心　北京　2003年）

正文：

中缀表达式的两种经典的计算方法，即转为后缀表达式法（间接法）与直接计算法。我们分别讨论这两种方法的优先级排序。

1.中缀转后缀表达式算法（间接法）

1.1需要什么样的数据结构？
- 一个运算符栈用来处理所有运算符，并将他们按正确的排序输出到后缀表达式中。
- 一个输出序列用来输出后缀表达式（可以用stack ，也可以用vector、string等，因为需要的操作只是在序列尾添加数据），可以记为操作数栈，因为遍历时遇到操作数直接压栈，但其中也会有运算符。
1.2运算规则是什么？

结合中缀表达式的计算规则及后缀表达式的计算规则：

中缀（人的计算）：

(1) 先计算括号内，后计算括号外；

(2) 在无括号或同层括号内，先乘除运算，后加减运算，即乘除运算的优先级高于加减运算的优先级；

(3) 同一优先级运算，从左向右依次进行。

后缀（计算机的计算）：

从左到右扫描后缀表达式，如果遇到操作数，将其压入栈中，如果遇到操作符，则从栈中弹出两个操作数，计算结果，然后把结果入栈，直到遍历完后缀表达式，则计算完成，此时的栈顶元素即为计算结果。

1.3优先级排序及操作步骤？

这种情况的优先级排序比较简单也易于理解，只将四则运算的优先级编码，记＋、－为 0，记 * 、 / 为1。
- 当遇到操作数的时候放入输出序列中。
- 当遇到运算符时情况变得复杂，由于运算符有不同的优先级，我们不能确定取到的运算符是否可以直接计算，需要和上一个操作符进行比较：如果优先级相等，说明是同一类型的运算符，应该从左到右进行运算，即先算栈顶运算符（出栈到输出队列），在把这个运算符压栈；如果该运算符优先级低，说明应该先进行栈内运算符的计算，直到该运算符比栈顶的高再压栈；如果该运算符优先级高，则直接压栈。可以看出，我们的运算符栈实际上是在维护一个严格递增的单调队列。
- 当遇到括号，如果左括号直接进栈，如果遇到右括号，需要依次取出栈中的运算符并输出，直到遇到左括号并弹出左括号（因为后缀表达式不存在括号）
- 遍历完之后将运算符栈依次弹出到输出序列
1.4代码示例
```
#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<locale>
using namespace std;

//判断是否为运算符
bool isops(string s) {
	if (s == "+" || s == "-" || s == "*" || s == "/")
		return true;
	else
		return false;
}

//定义运算符优先级
int icp(char c)
{
	if (c == '*' || c == '/')
		return 1;
	if (c == '+' || c == '-')
		return 0;
}

//中缀转后缀
vector <string> MidtoRPN(string s)
{
	vector<string> out;
	stack<string> sta;
	string str = "";
	int i = 0;
	while (i < s.size())
	{
		//1.读入操作数
		if (isdigit(s[i]))
		{
			str += s[i];
			i++;
			while (i < s.size() && isdigit(s[i]))
			{
				str += s[i];
				i++;
			}
			sta.push(str);
			str = "";
		}
		//2.读入开括号
		else if (s[i] == '(')
		{
			str += s[i];
			sta.push(str);
			str = "";
			i++;
		}
		//3.读入闭括号
		else if (s[i] == ')')
		{
			while (!sta.empty() && sta.top()[0] != '(')
			{
				out.push_back(sta.top());
				sta.pop();
			}
			sta.pop();//弹出左括号
			i++;
		}
		//4.读入运算符
		else
		{
			while (!sta.empty() && sta.top()[0] != '(' && icp(s[i]) <= icp(sta.top()[0]))
			{
				out.push_back(sta.top());
				sta.pop();
			}
			str += s[i];
			sta.push(str);
			str = "";
			i++;
		}
	}
	while (!sta.empty())
	{
		out.push_back(sta.top());
		sta.pop();
	}
	return out;
}

//后缀表达式求值
double evalRPN(vector<string>& tokens)
{
	double a, b;
	stack<double> sta;
	for (auto i : tokens)
	{
		if (!isops(i))
		{
			sta.push((double)stoi(i));
		}
		else
		{
			a = sta.top();
			sta.pop();
			b = sta.top();
			sta.pop();
			if (i == "+")
				sta.push(a + b);
			else if (i == "-")
				sta.push(b - a);
			else if (i == "*")
				sta.push(a * b);
			else if (i == "/")
			{
				if (a == 0)
				{
					cout << "除数不能为0" << endl;
					exit(0);
				}
				sta.push(b / a);
			}
		}
	}
	return sta.top();
}

//中缀表达式间接求值
double calculate(string s)
{
	vector<string> res = MidtoRPN(s);
	return evalRPN(res);
}

int main()
{
	double result = calculate("3*(7-2)");
	cout << result << endl;
	return 0;
}
```
2.中缀表达式直接求值

2.1与第一种方法思路有什么区别

大体思路相同，只是在第一种方法中，我们将从运算符栈中弹出的运算符输出到后置表达式中；而弹出的运算符不输出，而是从操作数栈取两个数直接进行运算，并把运算结果压入操作数栈。

2.2需要什么样的数据结构
- 一个操作数栈(nums)
- 一个运算符栈(ops)
2.3 运算符的优先级排序

该种方法下的优先级排序极为复杂，你可能看过下面这两种图

其实下面这张图就是按上面优先级的编码进行比较得到的图，可是为什么，为什么会是这样呢？

2.3.1什么是栈内优先级，什么是栈外优先级？

当遍历到一个运算符时，我们先不入栈，而将它的优先级与栈顶元素的优先级比较；当前遍历到的运算符在栈外，取栈外优先级，栈顶元素取栈内优先级，将这两种优先级进行比较。

2.3.2为什么要有栈内和栈外两种优先级，一种不行吗？

根据2.1的分析，这两种方法大体思路一样，直接求中缀表达式用一种优先级的排序是完全可以的，间接法也可以用栈内和栈外两种优先级算法。这两种方法使用时是等价的，而大家约定俗称的作法就是：转后缀表达式法用一种优先级排序，直接法用两种优先级排序，也许这就是经典8，咱也不太懂呢~

2.3.3两种优先级是怎么排的，意义是什么？

我们发现所有的二元运算符不管是在栈内还是栈外的优先级排序都是一样的：即乘方>乘除>加减。这与我们在前文的优先级排序相符，而这种双优先级排序的灵魂就在于将左括号 ( 、右括号）及 # 进行了编码。下面为运算符进栈的几种情况的编码分析：
- 对于 # ：我们用这个符号标志着表达式的开始和结束，若计算 "3*(7-2)" ，转为计算 "#3*(7-2)#" ，一开始先在运算符栈中放入一个 #, 再遇到一个#时，说明表达式已经结束，我们需要依次取出运算符栈中剩下的运算符进行运算，直到两个#相遇，程序结束，返回最终结果，因此，我们需要在遇到#时将栈中全部元素出栈，分析可知#的栈外优先级应该是最低的，编码为0；
- 对于 ( : 遇到左括号需要直接压栈，因此其栈外优先级应该比所有二元运算符的栈内优先级都高，编码为8；
- 对于）：遇到右括号，我们需要将左右括号之间的元素出栈，因此其栈外优先级应该比所有二元运算符的栈内优先级都低，编码为1；
- 当遇到左右括号相遇时，我们需要消除这一对括号，定义当栈外优先级和栈内优先级相等时消除，则左括号（的栈内优先级应该等于右括号）的栈外优先级，为1。
- 对于所有的二元运算符：宏观顺序是乘方>乘除>加减，而每一种类型的栈内外优先级都不相等，而是差1，这是因为当连续遇到两个同类型的运算符时，我们应该从左到右运算，即先算栈内的，再算栈外的，因此内比外要高。
可以看出，该运算符栈实际上也是在维护一个严格递增的单调队列。而通过将（、）、# 的编码，简化了上一种算法中括号匹配和表达式遍历结束剩余运算符出栈的步骤，使其和其它二元运算符一样通过编码参与运算，消除其特殊性。

1.4操作步骤

依次读入表达式中的每个字符,若是

•操作数,则进nums栈；

•运算符s1，则和ops栈中的栈顶元素s2做比较再操作。

1）若icp(s1)>isp(s2)，则s1入栈，接收下一字符；

2）若icp(s1)==isp(s2)，则ops中的栈顶元素出栈，接收下一字符。

3）若icp(s1)<isp(s2)，则从nums栈顶弹出两个操作数，与ops中的栈顶元素做运算，并将运算结果入nums栈,并不接收下一字符，因为栈内可能有多个比该字符优先级高的运算符，要一直进行二元运算的操作直至转为1或2的情况；

直至表达式扫描完毕。

1.5代码示例
```
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;

//栈内优先级
int isp(char ch)
{
	switch (ch)
	{
	case '#': return 0;
	case '(': return 1;
	case '^':return 7;
	case '*':case '/':case '%':return 5;
	case '+':case '-':return 3;
	case ')':return 8;
	}
}

//栈外优先级
int icp(char ch)
{
	switch (ch)
	{
	case '#': return 0;
	case '(': return 8;
	case '^':return 6;
	case '*':case '/':case '%':return 4;
	case '+':case '-':return 2;
	case ')':return 1;
	}
}

//比较栈内栈外优先级大小
char precede(int isp, int icp)
{
	if (isp < icp) return '<';
	else if (isp > icp) return '>';
	else return '=';
}

//计算最简单的双目运算符表达式
int cal(int first, char op, int second)
{
	switch (op)
	{
	case'+':
		return(first + second);
	case'-':
		return(first - second);
	case'*':
		return(first * second);
	case'/':
		return(first / second);
	case'%':
		return(first % second);
	case'^':
		return(pow(first, second));
	}
}

//计算中缀表达式
int middexpression(string s)
{
	s += '#';//表达式尾加#
	stack<char>ops;
	ops.push('#');//表达式头加#
	stack<int>nums;
	int num = 0, i = 0,first,second;
	while (s[i] != '#' || ops.top() != '#')// 字符扫描完毕且运算符栈仅有‘＃’时返回结束
	{
		//1.是数字
		if (isdigit(s[i]))
		{
			num = num*10 + (s[i] - '0');
			if (!isdigit(s[i + 1]))
			{
				nums.push(num);
				num = 0;
			}
			i++;
		}
		//2.是字符有三种情况
		else
		{
			switch (precede(isp(ops.top()), icp(s[i])))
			{
			case '<':// 栈顶元素优先权低
				ops.push(s[i]);
				i++;
				break;
			case '=':// 脱括号并接收下一字符
				ops.pop();
				i++;
				break;
			case '>':// 退栈并将运算结果入栈，但不取下一表达式字符
				second = nums.top();
				nums.pop();
				first = nums.top();
				nums.pop();
				nums.push(cal(first,ops.top(), second));
				ops.pop();
				break;
			}
		}
	}
	return nums.top();
}

int main()
{
	cout << middexpression("30*2^3*(7-2)") << endl;
	return 0;
}
```
收起
展开全文
中缀表达式

数据结构-栈-表达式求值

2021-09-13 11:49:12

表达式 ...一个操作数栈，用来存储表达式中的操作数；另一个是运算符栈，用来存储表达式中的运算符常见的表达式为中缀表达式，如 9 +（3-1）* 3 + 10 / 2 后缀表达式不含括号，如 9 3 1 - 3 * + 10 2

表达式

计算规则
从左到右，先乘除，后加减。有括号先算括号
构成元素
加（+）、减（-）、乘（*）、除（/）、括号（ () ），也可含空格（）
计算过程
先将中缀表达式转换成后缀表达式，再对后缀表达式进行具体求值。
在具体的代码实现中，两个步骤混在一起
需借助两个栈来实现计算。一个操作数栈，用来存储表达式中的操作数；另一个是运算符栈，用来存储表达式中的运算符

常见的表达式为中缀表达式，如 9 +（3-1）* 3 + 10 / 2
后缀表达式不含括号，如 9 3 1 - 3 * + 10 2 / +
优先级设定
优先级针对表达式中的运算符而言，分为栈内优先级、栈外优先级两种。

无论栈内栈外，乘除的优先级始终高于加减的优先级，乘除的优先级相同，加减的优先级相同
相同的运算符，栈内的优先级高于栈外的优先级
栈外，‘(’ 的优先级高于所有的运算符；栈内，则低于所有的运算符
（具体代码时，’ ( ’ 直接入栈）
栈外，‘)’ 的优先级低于所有的运算符；栈内，则高于所有的运算符。
（具体代码时，’ ) ’ 不会入栈）

之所以这样分栈内、栈外优先级，个人认为是缘于计算规则中的 “从左到右” 规定。
假设表达式中仅有两个相同优先级的运算符，如 1 + 2 -3。
设左侧的 + 运算符为 lope，右侧的 - 运算符为 rope。按照从左到右的计算规则，lope 应比 rope 先参与运算。
在具体代码实现中，需从左至右依次扫描表达式中的每个字符，lope 先入栈。当扫描到 rope 时（此时 rope 尚未入栈，而 lope 已经入栈），为了满足从左到右的计算规则（即实现先计算 lope 的目的），需赋予 lope（栈内）比 rope（栈外）更高的运算优先级。
简而言之，加减乘除运算符入栈后优先级升高

在这里插入图片描述
代码主要阅读顺序：main - fun，在 fun 中按需阅读额外的函数代码

#include <iostream>
#include <string>
#include <stack>
using namespace std;

bool isOpe(char ch) // 判是否为加减乘除运算符 
{
    switch (ch)
    {
    case '+':
    case '-':
    case '*':
    case '/':
        return true;
    default:
        return false;
    }
}
bool isNum(char ch)
{
    if ((ch - '0') >= 0 && (ch - '0') <= 9)
        return true;
    return false;
}
int cmp(char inStack, char outOfStack)
{
    /* 
		栈内运算符 inStack   栈外运算符  outOfStack
		前者优先级大，返回正数 1
		后者优先级大，返回负数 -1
		运算符栈内元素只可能为 # + — * / ( 
	*/ 
    switch (inStack)
    {
    case '+':
        if (outOfStack == '*' || outOfStack == '/')
        {
            return -1;
        }
        else
        {
            return 1;
        }
    case '-':
        if (outOfStack == '*' || outOfStack == '/')
        {
            return -1;
        }
        else
        {
            return 1;
        }
    case '*':
        return 1;
    case '/':
        return 1;
    case '(':
        if (outOfStack == '+' || outOfStack == '-' || outOfStack == '*' || outOfStack == '/')
        {
            return -1;
        }
    case '#':
        if (outOfStack == '+' || outOfStack == '-' || outOfStack == '*' || outOfStack == '/')
            return -1;
    }
}
double cal(char ch, double num1, double num2)
{
    switch (ch)
    {
    case '+':
        return num1 + num2;
    case '-':
        return num1 - num2;
    case '*':
        return num1 * num2;
    case '/':
        if (num2 == 0)
        {
            cout << "除数为0" << endl;
            exit(-2);
        }
        else
        {
            return num1 / num2;
        }
    }
}

double fun(string str)
{
    /*
		操作符栈 OpeStack 设为 char 型  
		操作数栈 NumStack 设为 double 型(考虑到除法运算)
		引入 STL 中的 stack 避免编写两种不同的栈相关代码（引入模板也可达到相同目的）	 
	*/
	stack<char> OpeStack;
    stack<double> NumStack;
    
    /*
	  初始时，OpeStack 为空，无法进行后续的 操作符优先级比较 运算，
	  故先入栈一个额外的字符 '#' 来满足后续计算，其优先级比栈内 '(' 低 
	*/ 
    OpeStack.push('#'); 
    
    /*
		表达式中的操作数位于 运算符和空格之间，
		操作数可能仅为 1 位，如 3，也可能多位，如 333 
		引入 num_flag 来标记操作数的第一位数 
		进而达到 让 多位的操作数 参与运算 的目的
	*/ 
    bool num_flag = false;
    
    // 从左到右，依次扫描表达式中的每个字符 
    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] == ' ') // 若字符为空格，则跳过 
        {
            continue;
        }
        else if (isNum(str[i])) // 若字符为数字，则接下来分析是否为多位的操作数 
        {
            /*
				以 12+ 为例
				扫描至 1 时，num_flag为 false ,表示其为数字 12 的第一位数字，
				    直接入栈 NumStack 即可，并修改 num_flag 为 true 
				扫描至 2 时，num_flag 为true，表示 2 不是 数字 12 的第一位数字
				    需从  NumStack 中取出 2 前面已入栈的数字，此为数字 1。 
				    故将 NumStack 栈顶 的 1 出栈，与 2 组成数字 12 后
				    再将完整的多位数数字 12 入栈  NumStack
				扫描至 + 时，非数字，num_flag 修改为 false，
					表示其前的多位数数字扫描完毕 
			*/ 
			
			if (num_flag) // 若为多位的操作数，则将相应字符进行转化为数字 
            {
               /* 
			     STL-stack 中, pop() 的返回类型为 void 
			     为达到使用 出栈元素 的目的，先取栈顶元素，后出栈该元素 
			   */ 
			    double temp = NumStack.top();
                NumStack.pop();
                temp = temp * 10 + str[i] - '0';
                NumStack.push(temp);
                num_flag = true;
            }
            else   
            {
            	// 标记操作数的第一位数，直接入栈该数
                NumStack.push(str[i] - '0');
                num_flag = true;     
            }
        }
        else if (isOpe(str[i]))  // 若扫描到加减乘除运算符，则与 OpeStack 的栈顶元素进行优先级比较 
        {
            num_flag = false;   // 表示其前的多位数数字扫描完毕 
            if (cmp(OpeStack.top(), str[i]) < 0) // 若栈外运算符的优先级大 
            {
                OpeStack.push(str[i]);
            }
            else
            {
            	/*
					若栈外运算符的优先级小
				*/
                while (cmp(OpeStack.top(), str[i]) > 0)
                {
                    double num1 = NumStack.top(); 
                    NumStack.pop();
                    double num2 = NumStack.top();
                    NumStack.pop();
                    char ch = OpeStack.top();
                    OpeStack.pop();
                    
                    /*
					 	表达式越左的操作数，越先入栈 NumStack 
						实际运算顺序 num2 ch num1 
					*/ 
                    double num3 = cal(ch, num2, num1); 
                    NumStack.push(num3);
                }
                OpeStack.push(str[i]);
            }
        }
        else if (str[i] == '(')   // '(' 直接入栈 
        {
            num_flag = false;
            OpeStack.push(str[i]);
        }
        else if (str[i] == ')')  // 扫描至 ')'时，依次出栈 OpeStack 元素参与运算，直至 '(' 
        {
            while (OpeStack.top() != '(')
            {
                double num1 = NumStack.top();
                NumStack.pop();
                double num2 = NumStack.top();
                NumStack.pop();
                char ch = OpeStack.top();
                OpeStack.pop();
                double num3 = cal(ch, num2, num1);
                NumStack.push(num3);   // 运算结果入栈 
            }
            OpeStack.pop();
        }
    }
    while (OpeStack.top() != '#')  // 将 OpeStack 中的剩余运算符出栈参与运算 
    {
        double num1 = NumStack.top();
        NumStack.pop();
        double num2 = NumStack.top();
        NumStack.pop();
        char ch = OpeStack.top();
        OpeStack.pop();
        double num3 = cal(ch, num2, num1);
        NumStack.push(num3);
    }
    return NumStack.top();
}
int main()
{
    string str;// 使用 string 字符串来获取表达式 
    cout << "输入一个表达式" << endl;
    cin >> str;
    cout << "运算结果为" << endl;
    cout << fun(str) << endl;
    return 0;
}

收起

展开全文

数据结构

四则运算的中缀表达式转后缀表达式思路整理
2020-09-01 00:01:22
本次复盘包含有中缀表达式转化为后缀表达式的全部思路。...然后根据运算过程，设计不同运算符优先级的高低。在难度上，从没有括号的四则运算开始，逐步升级，直至完成有括号的四则运算运算符优先级设计。
索引

中缀表达式与后缀表达式特点
为什么用栈结构？
优先级表格设计
带括号的四则运算
总结
中缀表达式与后缀表达式特点

中缀表达式定义及其相关内容
 后缀表达式定义及其相关内容

首先，四则运算中只有4个运算符和两个括号，分别为 +、-、*、/、(、)。这4个运算符都是双目运算符，也就是说每个运算符至少有两个运算目。

其次，中缀表达式的特点是两个运算目分别在运算符的两边，而后缀表达式的运算目按出现次序先后放在运算符的前面。

也就是说，在输出后缀表达式的时候，如果两个运算目尚未输出，则不得输出操作这两个运算目的运算符。

假设中缀表达式为：a+b-c
则后缀表达式应为：ab+c-
从左到右输出后缀表达式时，如果b尚未输出，则不得输出+

最后是四则运算符的优先级问题。众所周知， * 和 / 的优先级高于 + 和 -，当优先级相同时，按照中缀表达式由左向右逐个符号进行计算。

为什么用栈结构？

当我们操作后缀表达式的时候，如何按照正确的顺序输出运算符？

举例：

中缀表达式：
a+b*c-d

我们假设用一个数据结构存储运算符，用一个队列来存储输出顺序，然后按照从左往右的顺序逐个扫描中缀表达式。
- 首先扫描到运算目 a。运算目 a 是整个表达式的第一个，所以可以直接放入输出队列。
输出队列：a
数据结构：
- 然后我们扫描到运算符 + ，但是此时输出队列里没有 + 的第二个运算目，所以我们只能先把它放入数据结构里存放起来。
输出队列：a
数据结构：+
- 扫描到运算目 b 。运算目不能影响运算符的顺序，因此直接将它放入输出队列。
输出队列：ab
数据结构：+
- 此时我们还不能将 + 放入输出队列，因为我们还不能确定 b 是不是 + 的第二个运算目。（事实上它也确实不是，+ 的第二个运算目是 b*c 的值）
- 扫描到运算符 * ，现在我们可以确定了，实际上 b 是 * 的第一个运算目。出于和 + 同样考虑，我们把乘号放入数据结构。
输出队列：ab
数据结构：+*
- 扫描到运算目 c ，放入输出队列。
- 虽然四则运算中，乘除已经是优先级的天花板了，但是拓展到更广阔的领域，我们依然不能确定，乘除是最高的优先级，所以和加号一样，暂时不予输出。
输出队列：abc
数据结构：+*
- 扫描到运算目 - ，我们现在可以确定 c 是 * 的第二个运算目，所以我们将数据结构里的 * 放入输出队列。
输出队列：abc*
数据结构：+
- 此时，剩余在数据结构里的 + 和扫描中的 - 是同级关系，应该先计算 a+(b*c的值) 。所以 + 优先输出
输出队列：abc*+
数据结构：
- 此时我们仍未扫描到 - 的第二个运算目，所以我们把 - 放入数据结构中。
输出队列：abc*+
数据结构：-
- 扫描到运算目 d，放入到输出队列中
输出队列：abc*+d
数据结构：-
- 中缀表达式结束，我们可以确定 d 为运算符 - 的第二个运算目，所以将数据结构中的 - 放入到输出队列中。此时后缀表达式全部输出序列完成。
输出队列：abc*+d-
数据结构：

观察可以发现：+ 先于 * 进入数据结构，但却是 * 先被数据结构弹出，由此可见，按照该算法，该数据结构具有后进先出的特点，故采用栈结构。

优先级表格设计

计算机没有我们人这么聪明，所以我们需要用一些更直观的手段来描述优先级，于是有了优先级表 P

运算符 + / - * / /
优先级 0 1

根据上面的情况总结归纳：
- 如果扫描到运算目，则直接放入输出队列
- 如果扫描到运算符，则根据情况不同有三种情况：
1. 栈为空栈，则直接压入
2. 栈顶元素优先级高于或等于被扫描的运算符，则弹出栈顶至输出队列。被扫描运算符与新栈顶继续比较，直到被扫描运算符被压入栈内。（优先级高先运算规则和从左到右规则）
3. 栈顶元素优先级低于被扫描的运算符，则将被扫描的运算符压入栈内。
当中缀表达式被扫描完以后，后缀表达式就算是完成了。

但上述方法还可以简化，单独运行一个函数去判断栈空过于费劲，我们可以放入一个优先级最低的作为栈底。

新优先级表：

运算符 # + / - * / /
优先级 0 1 2

这样比较情况就只有两种，相对省事了一点。

带括号的四则运算

括号的引入改变了原有的计算顺序，所以需要进行一定修改。
括号内的算术内容要优先计算，所以从这个角度来讲，括号内的优先级高于括号外的优先级。

举例：

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

按照之前的算法逻辑，我们可以直接跳转到下面状态

当前扫描：(
输出队列：ab
栈：# + *
- 由于括号优先级要高于 * /，所以括号得以入栈。
- 扫描 c ，放入输出队列
当前扫描：c
输出队列：abc
栈：# + * (
- 扫描 + ，此时栈顶为 ( 优先级高于 +，如果按照之前优先级设计，加号将无法入栈。所以我们要对优先级设计进行修改。为此我们引入栈内优先级和栈外优先级。
栈内优先级(in stack priority，简写为：isp)：当运算符在栈内时所拥有的优先级。( 应持有最低的优先级才能让后续其他运算符入栈。#除外。
栈外优先级(in coming priority，简写为：icp)：当运算符在栈外时所拥有的优先级。( 应持有最高的优先级才能让自己得以入栈
运算符 # ( + / - * / /
栈内优先级（isp） 0 1 2 3
栈外优先级（icp） 0 4 2 3
- 因为 ( 的栈内优先级低于 + 的栈外优先级，所以 + 得以入栈
- 扫描 d
当前扫描：d
输出队列：abcd
栈：# + * ( +
- 扫描 /
当前扫描：/
输出队列：abcd
栈：# + * ( + /
- 扫描 e
当前扫描：e
输出队列：abcde
栈：# + * ( + /
- 扫描 )，此时按照后缀表达式的规则，应该将 / 弹出。所以 ) 的栈外优先级应该低于或等于 / 的栈内优先级。
- 同理，) 的栈外优先级应该低于或等于 + 的栈内优先级。
当前扫描：)
输出队列：abcde/+
栈：# + * (
- 此时栈顶为 ( ，后缀表达式中没有括号一说，所以 ( 被弹出，但不被放入输出队列。
- 至此，本括号内的所有算式结束，如果放任 ) 继续弹出其他运算符，则有可能使后缀表达式发生错误（双层括号的情况，自己推演）。因此，必须将 ( )比较的结果与 ) 和其他运算符比较的结果区分开来。
最终的运算符优先级表

运算符 # ( + / - * / / )
栈内优先级（isp） 0 1 3 5
栈外优先级（icp） 0 6 2 4 1

至此，只有括号匹配时，被扫描的栈外优先级和栈顶栈内优先级相等。除此之外，当被扫描的栈外优先级高于栈顶栈内优先级时，栈外元素入栈，反之，栈顶元素弹出并继续比对。

最终后缀表达式：abcde/+*+ -

总结

算法详述：
- 从左往右扫描中缀表达式
- 如果扫描到数字，加入后缀表达式
- 如果扫描到运算符
1. icp(‘被扫描运算符’) > isp(‘栈顶运算符’)，被扫描运算符入栈；继续扫描中缀表达式。
2. icp(‘被扫描运算符’) < isp(‘栈顶运算符’)，栈顶运算符弹出，加入后缀表达式；被扫描运算符继续比较新栈顶。
3. icp(‘被扫描运算符’) == isp(‘栈顶运算符’)，栈顶元素弹出，不加入后缀表达式；继续扫描中缀表达式。
运算符优先级表

运算符 # ( + / - * / / )
栈内优先级（isp） 0 1 3 5
栈外优先级（icp） 0 6 2 4 1
收起
展开全文
数据结构算法
【数据结构】使用栈实现的算符优先算法
千次阅读 2019-07-08 22:56:52

为了实现这个算法，我们需要两个栈，一个是符号栈OPTR，另一个是数据栈OPND，算符预先设定好优先级，当解析到数字的时候，将其入数据栈当解析到运算符的时候，比较它和之前一个运算符的优先级，如果比之前的优先级...

收起
Python中栈、队列与优先级队列的实现方法
2020-09-19 05:03:00

主要给大家介绍了关于Python中栈、队列与优先级队列的实现方法，文中通过示例代码介绍的非常详细，对大家学习或者使用python具有一定的参考学习价值，需要的朋友们下面来一起学习学习吧

收起
python 显式指定导入模块（优先级）
2019-12-12 10:19:51

在python中，一个文件夹和模块一样... 2、sys.path.append 当导入的模块不在默认的路径下可以使用该方法进行添加 3、sys.path.insert 该方式可以指定导入的优先级，指定的目录会优先于其他的路径先被import方式检索到。

收起

模块文件夹
详解：操作符的优先级
2021-08-02 15:27:02

下面给出详细的操作符的优先级表格，从上至下优先级依次递减（越靠近上面，操作符的优先级越高） Ps：我们写出的表达式如果不能通过操作符的属性确定唯一的计算路径，那这个表达式就是存在问题的，在写...

收起

c语言
c语言有没有栈和优先级队列的头文件？
2022-05-04 17:04:25

c语言中有没有自带的栈或者优先级队列的头文件，像c++的queue一样？我也是服了百度了，现在百度什么都是一样没什么作用的东西。

收起

c语言
AcWing 3302. 表达式求值 (栈，运算符优先级)
2021-05-08 10:07:45

} else { //一直计算栈顶优先级高的操作符，直到栈空或遇到优先级低的 while(op.size() && h[op.top()] >= h[s[i]]) eval(); op.push(s[i]);//操作符入栈 } } while(op.size()) eval(); cout () ; return 0; }

收起
操作符优先级全列表，一览表
千次阅读 2017-08-04 10:49:19

在一个表达式中可能包含多个有不同运算符连接起来的、具有...优先级从上到下依次递减，最上面具有最高的优先级，逗号操作符具有最低的优先级。表达式的结合次序取决于表达式中各种运算符的优先级。优先级高的运算符先

收起

运算符操作符
栈实现算数优先级的运算C
2009-11-17 22:35:37

数据结构实验。。。用栈实现算数优先级的运算，vc6。0中实现，

收起
python笔记(爬虫scrapy框架 redis 队列和栈，优先级)
千次阅读 2019-05-14 20:39:44

一、redis 队列和栈方式一 import redis class LifoQueue(object): """Per-spider LIFO queue.""" def __init__(self): self.server = redis.Redis(host='140.143.227.206',port=8888,password='beta') ...

收起

python
调用C++中的栈，队列和优先级队列库函数
千次阅读 2014-11-26 20:48:40

C++中栈和队列的调用使用标准库中的栈和队列，相关头文件 #include #include 定义栈如下： stack stk; 1.s.empty() 如果栈空就返回true，否则返回false； 2.s.size() 返回栈中元素的个数 3.s.pop() ...

收起

c++ 队列
后序表达式的转换与计算的原理及实现
2021-05-04 10:19:01

本篇博客部分内容出自《2022数据结构考研复习指导》，仅作个人学习记录。这里写目录标题一、中序表达式转后序表达式的... 后序表达式的运算符在操作数后面，在后序表达式中已经考虑了运算符的优先级，没有括号，只

收起
嵌入式技术栈之RTOS的优先级翻转问题
2022-04-12 12:50:07

优先级翻转问题。

收起

嵌入式
栈、队列及优先级队列
2019-09-29 03:58:33

栈、队列及优先级队列都可以使用数组链表来实现，优先级队列通常使用堆实现。在栈、队列及优先级队列中，访问是受限制的，在某一时刻只有某一个特定的数据项可以被读取或删除。栈应用：单词逆序...

收起
C++运算符优先级
2018-03-20 23:03:02

收起
C++中缀表达式转后缀表达式
千次阅读 2019-11-11 23:06:03

C++中缀表达式转后缀表达式最近在看计算器相关的...isp栈内元素优先级(in stack priority) icp栈外元素优先级(in coming priority) 2.算法思想 (1)初始化栈，将结束符‘#’入栈，在输入字符串末尾添加’#’。...

收起

C++
初级计算器算法（栈处理运算符优先级）
千次阅读 2014-10-25 15:46:32

运算符的先后计算可以用栈来保存，分别有几种情况 1，当前1+2-3即优先级相同，那么可以先算前一个。 2,1+2*3这种情况我不做处理（注：我每次只选择是否处理上一个） 3,2*8+2这种情况计算前一个。小细节太多，不说太...

收起
stack&&queue 和优先级队列的介绍和实现
2022-03-31 20:48:40

栈的实现可以放在链表中，也可以放在数组中等等，对于C++的栈，我们没必要像C语言一样，用什么容器就把什么容器实现出来，这样成本太高，我们可以用一个容器模板，在私有成员定义一个容器类的成员变量，相当于实例化...

收起

c++ 算法数据结构
activity生命周期、线程优先级、异常销毁、任务栈
2015-12-04 16:37:57

activity生命周期、线程优先级、异常销毁、任务栈参考代码

收起
C语言算符优先级（精华）
2021-05-24 00:37:28

int k=15,t;t=k&&k==5&&++k;运行后得到的 k为什么是 15不是16 ？...的优先级低于==，++，且它的结合性为左结合性==的优先级低于++，且它的结合性为左结合性++的优先级这这个表达式中最高，且它...

收起
安卓开发框架工具类相关-activity生命周期线程优先级异常销毁任务栈.zip
2019-07-29 16:19:39

activity生命周期、线程优先级、异常销毁、任务栈.zip,太多无法一一验证是否可用，程序如果跑不起来需要自调，部分代码功能进行参考学习。

收起
栈，队列，优先队列详解
2021-09-27 22:23:39

栈，队列，优先队列详解栈的概念，应用与实现队列的概念，应用与实现优先队列的概念应用与实现栈的概念，应用与实现一. 栈的概念首先栈是一个后进先出的数据结构，对于栈来说，只有一种插入和删除的方式就是通过...

收起

数据结构 c++
优先级栈的实现
2017-10-14 20:32:02

基础题，实现数据结构=》注意：c++容器的应用忘光了，复习吧 class Solution { public: vectorv; void push(int value) { v.push_back(value); } void pop() { v.pop_back(); ...

收起
使用栈结构将中缀表达式转为后缀表达式(使用枚举存储符号优先级等信息)
千次阅读 2019-08-02 16:09:42

建立一个栈S 。从左到右读表达式，如果读到操作数就将它压入栈S中，如果读到运算符则取出由栈顶向下的2项按操作数运算，再将运算的结果代替原栈顶，压入栈S中。如果后缀表达式未读完，则重复上面过程，最后输出栈顶...

收起

线性结构 Java实现
C#利用栈实现加减乘除运算
2021-01-01 12:06:35

关于优先级，两个括号(，)优先级最低，其次是+、-,最高的是*、/ 关于运算法则，打个比方，”(3+5*4)+3″这个串首先遇到左括号，直接压入运算符栈，然后是3，直接压入数栈，然后遇到5，压入数栈，遇到*，将其压入...

收起
Linux线程属性及优先级设置
2021-05-23 08:20:50

POSIX.1线程属性及优先级设置By zieckeyAll Right Reserved线程的属性由pthread_attr_t结构类型表示。在使用pthread_attr_t之前，需要调用pthread_attr_init对其初始化。pthread_attr_init为pthread_attr_t结构里面...

收起

运算符	`#`	`(`	`+` / `-`	`*` / `/`
栈内优先级（isp）	0	1	2	3
栈外优先级（icp）	0	4	2	3

运算符	`#`	`(`	`+` / `-`	`*` / `/`	`)`
栈内优先级（isp）	0	1	3	5
栈外优先级（icp）	0	6	2	4	1

运算符	`#`	`(`	`+` / `-`	`*` / `/`	`)`
栈内优先级（isp）	0	1	3	5
栈外优先级（icp）	0	6	2	4	1

一、栈

二、队列

三、优先级队列

中缀表达式计算中栈内优先级、栈外优先级的排序原理

前言：

引用：

正文：

1.中缀转后缀表达式算法（间接法）

2.中缀表达式直接求值

数据结构-栈-表达式求值

表达式

四则运算的 中缀表达式 转 后缀表达式 思路整理

索引

中缀表达式与后缀表达式特点

为什么用栈结构？

优先级表格设计

带括号的四则运算

总结

【数据结构】使用栈实现的算符优先算法

Python中栈、队列与优先级队列的实现方法

python 显式指定导入模块（优先级）

详解：操作符的优先级

c语言有没有栈和优先级队列的头文件？

AcWing 3302. 表达式求值 (栈，运算符优先级)

操作符优先级全列表，一览表

栈实现算数优先级的运算C

python笔记(爬虫scrapy框架 redis 队列和栈，优先级)

调用C++中的栈，队列和优先级队列库函数

后序表达式的转换与计算的原理及实现

嵌入式技术栈之RTOS的优先级翻转问题

栈、队列及优先级队列

C++运算符优先级

C++中缀表达式转后缀表达式

初级计算器算法（栈处理运算符优先级）

stack&&queue 和优先级队列的介绍和实现

activity生命周期、线程优先级、异常销毁、任务栈

C语言算符优先级（精华）

安卓开发框架工具类相关-activity生命周期线程优先级异常销毁任务栈.zip

栈，队列，优先队列详解

优先级栈的实现

使用栈结构将中缀表达式转为后缀表达式(使用枚举存储符号优先级等信息)

C#利用栈实现加减乘除运算

Linux线程属性及优先级设置

四则运算的中缀表达式转后缀表达式思路整理